[백준] 11403 - 경로 찾기 (Javascript / node)

문제

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

11403번: 경로 찾기

풀이

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
// N : 정점의 개수
const N = Number(input[0]);
const graph = [];
for(let i = 1; i<=N; i++){
  const target = [];
  input[i].split(" ").forEach((v,idx) => {
    if(v === "1") target.push(idx);
  })
  target.length > 0 ? graph.push(target) : graph.push([-1])
}

const dfs = (i,j, visited) => {
  for(const x of graph[i]){
    if(x < 0) return false;
    if(!visited[x]) {
      visited[x] = true;
      if(x == j) return true;
      if(dfs(x,j, visited)) return true;
    }
  }
  return false;
}

const answer = [];
for(let i =0; i<N;i++){
  const row = [];
  for(let j=0; j<N; j++){
    const visited = Array(N).fill(false);
    const res = dfs(i,j,visited) ? 1 : 0;
    row.push(res);
  }
  answer.push(row);
}
console.log(answer.map(v=> v.join(' ')).join('\n'));

 

1. 정점의 갯수 N을 구한다.

2. 정점마다의 간선(정점마다 연결된 선)을 graph에 저장

3. 연결된 간선이 없다면 해당 정점은 -1로 표시

4. dfs에서 중복으로 방지를 위해 visited로 방문한 정점을 체크

5. i -> j로 연결되어 있다면 1을 반환 아니라면 0을 반환

 

주의할점은 처음 0,0은 연결되어있는 간선으로 확인된 것이 아니기 때문에 간선인 graph의 정점에서 연결될때 true를 반환해야 한다.