[알고리즘/백준/13023] ABCDE(Node.js, BFS)

문제

---

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

13023번: ABCDE

 

풀이

---

문제를 읽고 숫자고르기와 같이 각 요소에서 DFS 탐색을 해야 한다는 걸 알 수 있었다.

주어진 입력으로 양방향 그래프를 만들고, 각 1~N에서 각각 방문 표시 배열(ch)을 이용한 DFS를 한다.

이때 flag 변수를 사용하여 연결된 노드가 5개가 나오는 경우 return 해서 DFS를 종료한다.

또한 flag가 1인 경우, 즉 A, B, C, D, E가 존재하는 경우, for문을 종료한다. flag가 1이면 1을 아니면 0을 출력한다. 

 

처음에는 DFS에서 연결된 개수를 반환해주고, 다 돌고 나왔을 때 그 개수가 5개라면 1 아니면 0을 반환하면 된다고 생각했다.

그래서 처음에는 DFS 값을 계속 반환해서 올려줬는데, 그랬더니 DFS에서 나왔을 때 방문표시를 풀어줄 수 없었다.(ch[nx] = 0)

각 노드 i에서 연결된 노드 nx를 탐색할 때 이전 nx에서 탐색했던 노드들은 방문 표시를 풀어줘야한다. 

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

const [N, M] = n.split(" ").map(Number);
const map = arr.map((row) => row.split(" ").map(Number));
let flag = 0;
const graph = Array.from({ length: N }, () => []);
for (let [from, to] of map) {
  graph[from].push(to);
  graph[to].push(from);
}

let ch;

function DFS(i, cnt) {
  if (cnt >= 5) {
  	// 5개 이상 연결되어 있는 경우 ABCDE 존재 O
    flag = 1;
    return;
  } else {
    for (let k = 0; k < graph[i].length; k++) {
      const nx = graph[i][k];

      if (ch[nx] === 0) {
        ch[nx] = 1;
        DFS(nx, cnt + 1);
        ch[nx] = 0; 
      }
    }
  }
}

// 각 숫자에서 DFS
for (let i = 0; i < N; i++) {
  ch = Array.from({ length: N }).fill(0);

  ch[i] = 1;
  DFS(i, 1);

  if (flag) break;
}

console.log(flag ? 1 : 0);