[백준 11403 - Node.js] 경로 찾기

 

🔗 문제 링크

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

11403번: 경로 찾기

✏️ 풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const N = +input[0];
const graph = input.slice(1).map(v => v.split(' ').map(Number));

const output = [...Array(N)].map(() => Array(N).fill(0));
const dfs = (node, start, visited) => {
  for (let i = 0; i < N; i++) {
    if (graph[node][i] && !visited[i]) {
      visited[i] = true;
      output[start][i] = 1;
      dfs(i, start, visited);
    }
  }
};

for (let i = 0; i < N; i++) {
  const visited = Array(N).fill(false);
  dfs(i, i, visited);
}

console.log(output.map(v => v.join(' ')).join('\n'));

각 정점들에서 시작해서 DFS로 갈 수 있는 모든 칸을 방문하고 방문이 가능한지 여부를 인접행렬 형태로 출력하면 된다.

 

output은 N * N 배열이고, 모든 칸이 0으로 초기화되어 있다.

DFS를 하면서 각 정점(i)별로 정점 j를 방문할 때마다 output[i][j]를 1로 변경시켜준다.

여기서 주의해야할 점은 output[i][i] (j = i)의 경우는 항상 1이 아니라, 다른 정점을 통해 정점 i를 방문할 수 있는 경우를 나타낸다. 따라서 dfs 내부에서 바로 방문 여부를 갱신하지 않고 방문 가능한 다른 정점들부터 방문 여부를 갱신하였다.

 

각 정점별로 dfs를 실행한 후에 output을 인접행렬 형태로 출력하였다.