백준 15723 n단 논법 (node.js)

문제

https://www.acmicpc.net/problem/15723

 

 

문제 해석

이 문제는 다른 그래프 이론과 비슷하다.

다만, 순회할 배열을 만들때 알파벳을 그대로 만들 수 없으니, 아스키 코드로 변경 후 풀면 된다.

 

풀이

const filePath = process.platform === "linux" ? "dev/stdin" : "../test.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");

function solution(input) {
  const N = +input.shift();
  const premise = input.slice(0, N).map(v => v.split(' '));
  const after = input.slice(N);
  const M = +after.shift();
  const conclusion = after.map(v => v.split(' '));
  const answer = [];

  const graph = Array.from({ length: 26 }, () => []);

  for (const [first, , second] of premise) {
    const from = first.charCodeAt(0) - 'a'.charCodeAt(0);
    const to = second.charCodeAt(0) - 'a'.charCodeAt(0);
    graph[from].push(to);
  }


  function dfs(from, target) {
    const visited = Array(26).fill(false);
    const queue = [from];
    visited[from] = true;

    while (queue.length > 0) {
      const cur = queue.shift();
      if (cur === target) return true;

      for (const next of graph[cur]) {
        if (!visited[next]) {
          visited[next] = true;
          queue.push(next);
        }
      }
    }

    return false;
  }

  for (const [first, , second] of conclusion) {
    const from = first.charCodeAt(0) - 'a'.charCodeAt(0);
    const to = second.charCodeAt(0) - 'a'.charCodeAt(0);

    if (dfs(from, to)) {
      answer.push('T');
    } else {
      answer.push('F');
    }
  }
  return answer.join('\n');
}

console.log(solution(input));

 

 

끝