[백준] 13023번 ABCDE - JavaScript(NodeJS)

문제

13023번: ABCDE

 

풀이

상당히 고생했던 문제이다.

 

이 문제는,

A와 B가 친구, B와 C가 친구, C와 D가 친구, D와 E가 친구인 경우가 존재하는지 구하면 된다.

우측과 같이 연속된 5명의 관계를 발견하면 된다.

 

그림과 같이 특정 노드에서 시작해서, 중복되지 않는 노드로 4번 이동할 수 있다면 (총 5개의 노드를 방문하면) 된다.

DFS를 이용할 것이며, 그래프의 연결관계 표현을 위해 인접행렬을 이용하자.

 

변수 소개

각 변수들은 아래에 작성한 코드를 참고하자.

 

N, M : 문제의 조건인 사람의 수(N), 관계의 수(M)
adjM : N * N 인접행렬
check : 방문한 노드를 재방문하지 않기 위한 배열. 방문시 1, 미방문시 0
flag : 정답을 발견했을 때 재귀를 빠르게 종료하기 위한 변수
dfs : DFS를 위한 함수. L은 현재 노드(사람), cnt는 서로 노드 간 연속 이동 횟수

 

코드

const sol = (input) => {
  const [N, M] = input[0].split(" ").map((v) => +v);
  const adjM = Array.from({ length: N }, () => Array(N).fill(0));
  const check = Array.from({ length: N }, () => 0);
  let flag = 0;
  for (let i = 1; i <= M; i++) {
    const [a, b] = input[i].split(" ").map((v) => +v);
    adjM[a][b] = adjM[b][a] = 1;
  }

  const dfs = (L, cnt) => {
    check[L] = 1; // 방문처리를 한다.
    if (flag) return; 
    if (cnt === 4) { // cnt가 4일 시 조건을 만족한다.
      flag = 1;
      return;
    }

    for (let i = 0; i < N; i++) {
      if (adjM[L][i] === 1 && !check[i]) { // 인접한 노드이며, 방문하지 않은 노드일 때 이동한다.
        dfs(i, cnt + 1);
      }
    }
    check[L] = 0; // 방문이 끝났다면 미방문으로 바꾼다.
  };

  for (let i = 0; i < N; i++) {
    dfs(i, 0); // 처음으로 방문할 노드를 선택한다.
  }
  return flag; // flag가 있다면(검출되었다면) 1을 출력, 아니라면 0을 출력.
};

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

최종적으로 다음과 같이 코드를 작성했다.

 

작성한 글의 흐름으로 보면, 바로 문제를 해결한 듯 보이나...

사실 무수한 실패 메시지가 떴었고 결국엔 시간초과 이슈로 좌절했던 문제다.

 

 

 

사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)

문제 조건을 다시 보며 고민을 하던 중 기억 저 멀리 인접 리스트가 생각이 났다.

인접리스트를 적용해보자.

 

인접리스트

인접행렬이 N * N 크기로 노드 간 연결 관계를 표현했다면,
인접리스트는 N * k 크기로 각 노드에 연결된 노드만을 리스트에 담은 것이다.

 

(0, 1), (0, 3), (1, 3)의 연결관계가 있다고 가정하고,
인접행렬과 인접리스트로 각각 나타내보면

 

인접행렬

0 [0, 1, 0, 1]
1 [1, 0, 0, 1]
2 [0, 0, 0, 0]
3 [1, 1, 0, 0]

인접리스트

0 [1, 3]
1 [0, 3]
2 []
3 [0, 1]

다음과 같이 표현한다.

 

표현해야 할 노드가 많아질 수록, 인접리스트가 유리할 것임은 분명하다.

 

아무튼 인접리스트를 선언해서, 다시 정보를 담은 후 dfs를 실행해보자.

 

인접리스트 코드

const sol = (input) => {
  const [N, M] = input[0].split(" ").map((v) => +v);
  const adjArr = Array.from({length:N}, ()=>Array(0)}; // N개의 행을 가지며 행마다 빈 배열을 하나씩 가진다.
  const check = new Array(N).fill(0);
  let flag = 0;
  for (let i = 1; i <= M; i++) {
    const [a, b] = input[i].split(" ").map((v) => +v);
    adjArr[a].push(b);
    adjArr[b].push(a);
  } // 인접리스트에 a->b, b->a 관계를 각각 넣어준다.

  const dfs = (L, cnt) => {
    if (flag) return; // 조건을 만족하면 빠르게 재귀를 종료하기 위한 조건문.
    check[L] = 1; // 노드를 방문한다.
    if (cnt === 4) {
      flag = 1;
      return;
    }

    for (let i = 0; i < adjArr[L].length; i++) { // 현재 노드의 인접리스트인 addArr[L] 크기 이용
      const next = adjArr[L][i]; // 다음에 이동할 수도 있는 노드
      if (!check[next]) { // next 노드에 방문하지 않았다면, 방문하자.
        dfs(next, cnt + 1);
      }
    }
    check[L] = 0; // 방문했던 노드는 다시 미방문 처리한다.
  };

  for (let j = 0; j < N; j++) {
    dfs(j, 0); // 처음 방문할 노드를 선택한다.
  }
  return flag;
};

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

다음과 같이 인접 리스트를 이용하면, 시간초과 이슈 없이 문제를 해결할 수 있다.