[백준] 16947번 서울 지하철 2호선 - JavaScript(NodeJS)

문제

 

16947번: 서울 지하철 2호선

지하철 2호선

 

풀이

 

정답 코드만 보고 싶으신 분은 맨 아래 코드를 참고!

 

이전 문제였던 (Two Dots 문제)[https://gobae.tistory.com/35] 에서 힌트를 얻었다.

 

이 문제에서는 2번의 절차가 필요해 보였다.

 

1. 사이클(순환선)에 해당하는 노드들을 구한다.
2. 모든 노드들을 조회하면서, 사이클까지의 최단거리를 구한다.

 

대충 이해한 바로는,
1번 절차는 dfs 쓰고, 2번 절차는 bfs를 쓰면 해결이 될 듯 했다.

 

시간초과 이슈에 대한 공포가 몰려오긴 했지만, 우선 시도해보자.

생각보다 코드가 꽤 길어져서 이번 포스팅에서는 풀어서 써보겠다.

 

0. 기본 입력 받기

 

입력을 받아, 인접 리스트를 생성하여 노드별로 이동 가능한 노드를 리스트로 넣었다.

// 백준에서 입력을 받는 코드
const input = [];
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input.push(line);
  })
  .on("close", () => {
    console.log(sol(input));
    process.exit();
  });

// 실행할 함수
const sol = (input) => {
  const N = +input[0];
  input = input.slice(1);
  const adjArr = Array.from({ length: N + 1 }, () => Array()); // 인접리스트 생성
  input.map((val) => { // map함수를 이용해서 인접리스트에 (from,to), (to,from) 정보를 넣는다.
    const [from, to] = val.split(" ").map((v) => +v);
    adjArr[from].push(to);
    adjArr[to].push(from);
  });
}

 

1. 사이클에 해당하는 노드 구하기

절차

깊이우선탐색 dfs를 이용한다.

 

인접리스트에서 현재 노드와 인접한 노드의 방문 여부를 탐색한다.
     만약. 미방문이라면 => 방문한다.
     방문했다면 => 이미 방문한 노드가 3개 이상이고 이동하려는 노드가 시작 노드인지 판별한다.

          위의 두 조건에 부합한다면, 사이클이므로 재귀를 탈출한다.

 

탈출하면서 노드의 방문 여부가 담긴 배열을 cycle 배열에 따로 복사해둔다.

 

사이클이 발견되지 않는다면, 다음 노드를 시작점으로 하여 위의 과정을 반복한다.

 

const sol = (input) => {
  ...

  const check = new Array(N + 1).fill(0); // 방문 여부를 조회할 배열
  let flag = 0;
  let cycle;

  function dfs(L, idx) {
    if (flag) return;

    for (let x of adjArr[idx]) {
      if (!check[x]) {
        check[x] = 1; // 체크 배열은 방문시 체크하고 빠져나올 때 해제해 줘야 한다.
        dfs(L + 1, x);
        check[x] = 0;
      } else if (L >= 3 && x === start) {
        flag = 1;    // 방문한 노드가 3개 이상이며, 다음 노드가 시작 노드라면 사이클이다.
        cycle = check.slice(); // 탈출 시 체크 배열을 복사한다.
        return;
      }
    }
  }

  let start;
  for (let i = 1; i <= N; i++) {
    start = i;
    check[i] = 1;
    dfs(1, i);
    check[i] = 0;
    if (flag) break;
  }
}

주의해야 할 점은,

1. 사이클을 발견하기 위해서, 노드의 방문 여부를 판단하면서 탈출 조건을 넣어줘야 한다.
2. 탈출할 때 cycle=check로 체크 배열을 가져오려 하면 0으로 가득 찬 배열을 얻을 것.. slice 메서드를 꼭 써주자.

 

2. 노드로부터 사이클까지의 최단거리를 구한다.

절차

최단거리에 유리한 너비우선탐색 bfs를 이용한다.

 

여기서는 1번에서 사이클을 구하면서 얻었던, 체크 배열이 담긴 cycle 배열을 적극 활용해보자.

 

만약 k번 노드의 최단거리를 구한다고 가정하자.
cycle[k]=1 이면 해당 노드는 사이클 내 노드이므로 바로 0을 출력하면 된다.
cycle[k]=0 이면 해당 노드는 사이클에 존재하지 않는 노드이므로, bfs를 활용해 최단거리를 구한다.

 

bfs에서는 큐를 활용한다.
최단거리를 구하기 위해서 dist 변수를 도입할 것인데, dist변수는 시작 노드에서의 거리를 나타낼 것이다.
유의할 점은 현재 큐에 담긴 모든 노드를 방문하고 나서 거리를 1 늘려줘야 한다.

 

무슨 말이냐면,
3 -> (1, 2) 로 방문할 때 1을 늘려주고,
1 -> (5), 2->(6,7) 1를 늘려줘야 한다.

 

즉 이전에 큐에 넣은 모든 노드의 정보를 큐에 넣고 나서! 거리를 1 늘려줘야 한다.

그러기 위해서는 큐에서 이동할 노드를 shift하기 전에, 현재 큐에 담긴 크기 만큼만 shift를 해주면 된다.

 

인접리스트를 조회하면서 다음에 이동할 수 있는 노드가 cycle에 존재하면, 무한루프를 탈출하며 dist 값을 반환해주자.

 

말로 하니까 좀 복잡해졌는데, 코드로 보는게 더 쉬울 듯 하다.

const sol = (input) => {
  ...
  function bfs(i) {
    const queue = [];
    queue.push(i);
    let dist = 0;
    const check2 = new Array(N + 1).fill(0); // 여기서도 방문 여부를 조회할 것인데, 사실 생략해도 정답은 나온다.
    check2[i] = 1;
    while (true) {
      dist++; // 큐에서 shift가 진행되기 전에 거리를 1씩 증가시키자.(원래는 for(iterator)가 끝나고 뒀는데 이게 더 보기 편하다)
      const iterator = queue.length; // 큐에는 계속 shift되면서 연결된 노드가 담기므로, 현재 큐의 크기만큼 반복한다.
      for (let i = 0; i < iterator; i++) { // 현재 큐의 크기로 반복해야 dist 변수를 증가시키는 시점을 잡을 수 있다.
        const from = queue.shift();
        for (let to of adjArr[from]) { // 인접리스트에서 인접한 노드 정보를 가져와보자.
          if (cycle[to]) { // 사이클에 존재한다면 거리를 반환하며 무한루프를 빠져나온다.
            return dist;
          }
          if (!check2[to]) {
            check2[to] = 1;
            queue.push(to); // shift한 노드와 연결된 노드들을 담아준다.
          }
        }
      }
    }
  }

  let result = [];
  for (let i = 1; i <= N; i++) {
    if (cycle[i]) { // 노드가 사이클에 있으면 bfs를 실행할 필요가 없다.
      result.push(0);
      continue;
    }
    result.push(bfs(i)); // 사이클에 없다면 bfs를 실행해서 최소거리 정보를 담아주자.
  }
  return result.join(" ");
};

이 코드에서 중요한 것은, 거리 변수 dist의 값을 올리는 시점이다.

 

시작한 노드에서부터의 거리를 구해야 하기 때문에, 각 단계마다 큐에 담긴 모든 노드의 조회가 끝나야 증가하는 것!

아무튼 기나긴 여정을 마치고, 최종 코드를 보자.

 

최종 코드

const sol = (input) => {
  const N = +input[0];
  input = input.slice(1);
  const adjArr = Array.from({ length: N + 1 }, () => Array());
  input.map((val) => {
    const [from, to] = val.split(" ").map((v) => +v);
    adjArr[from].push(to);
    adjArr[to].push(from);
  });
  const check = new Array(N + 1).fill(0);
  let flag = 0;

  let cycle;
  function dfs(L, idx) {
    if (flag) return;

    for (let x of adjArr[idx]) {
      if (!check[x]) {
        check[x] = 1;
        dfs(L + 1, x);
        check[x] = 0;
      } else if (L >= 3 && x === start) {
        flag = 1;
        cycle = check.slice();
        return;
      }
    }
  }

  let start;
  for (let i = 1; i <= N; i++) {
    start = i;
    check[i] = 1;
    dfs(1, i);
    check[i] = 0;
    if (flag) break;
  }

  function bfs(i) {
    const queue = [];
    queue.push(i);
    let dist = 0;
    const check2 = new Array(N + 1).fill(0);
    check2[i] = 1;
    while (true) {
      dist++;
      const iterator = queue.length;
      for (let i = 0; i < iterator; i++) {
        const from = queue.shift();
        for (let to of adjArr[from]) {
          if (cycle[to]) {
            return dist;
          }
          if (!check2[to]) {
            check2[to] = 1;
            queue.push(to);
          }
        }
      }
    }
  }

  let result = [];
  for (let i = 1; i <= N; i++) {
    if (cycle[i]) {
      result.push(0);
      continue;
    }
    result.push(bfs(i));
  }
  return result.join(" ");
};

const input = [];
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input.push(line);
  })
  .on("close", () => {
    console.log(sol(input));
    process.exit();
  });

 

상당히 길고 구려보이긴 하지만 나름 뿌듯한 해결이었다.