[BOJ][🟡5][백준#13023] ABCDE

문제 출처

BAEKJOON Online Judge #13023

문제

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다. 오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

A는 B와 친구다. B는 C와 친구다. C는 D와 친구다. D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다. 둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

출력

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

예제

예제 1

입력

5 4
0 1
1 2
2 3
3 4

출력

1

예제 2

입력

5 5
0 1
1 2
2 3
3 0
1 4

출력

1

예제 3

입력

6 5
0 1
0 2
0 3
0 4
0 5

출력

0

예제 4

입력

8 8
1 7
3 7
4 7
3 4
4 6
3 5
0 4
2 7

출력

1

My Sol

import sys
input = sys.stdin.readline

def dfs(u, i):
    global stack, arr
    if i == 5: return True
    for v in arr[u]:
        if v in stack: continue
        stack.append(v)
        if dfs(v, i+1): return True
        stack.pop()
    return False

N, M = map(int, input().split())
arr = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(int, input().split())
    arr[u].append(v)
    arr[v].append(u)

stack = []
ans = 0
for i in range(N):
    if dfs(i, 0):
        ans = 1
        break

print(ans)

dfs를 활용해 문제를 풀었다.

1. 모든 관계를 양방향으로 하여 2차원 배열에 저장한다.
2. 0부터 N-1까지 모든 지점을 0부터 하여 dfs를 실시한다.
3. dfs는 시작점인 u와 연결된 모든 v에 대하여 stack에 존재하지 않는 새로운 관계인 경우 더 깊이를 깊게 하여 연결해나간다.
4. stack이 중복되지 않는, 즉 5개의 관계 깊이까지 내려갔다면 True를 반환한다.
5. 그렇다면 문제의 요구사항을 충족한 것이므로 ans를 1로 바꾸고 종료한다.
6. ans를 출력한다.

결과

맞았습니다!!

의문점

사실 Node.js로 문제를 먼저 풀었었다.

const fs = require("fs");
const [NM, ...rels] = fs
  .readFileSync('/dev/stdin')
  // .readFileSync("./t.txt")
  .toString()
  .split("\n")
  .map((a) => a.trim());

const [N, M] = NM.split(" ").map(Number);
const arr = [];
for (let i = 0; i < M; i++) {
  arr.push([]);
}
rels.forEach((rel) => {
  const [u, v] = rel.split(" ").map(Number);
  arr[u].push(v);
  arr[v].push(u);
});

const stack = [];
const dfs = (u, n) => {
  if (n === 5) return true;
  for (v of arr[u]) {
    if (stack.includes(v)) continue;
    stack.push(v);
    if (dfs(v, n + 1)) return true;
    stack.pop();
  }
};

let ret = 0;
for (let i = 0; i < N; i++) {
  if (dfs(i, 0)) {
    ret = 1;
    break;
  }
}
console.log(ret);

거의 똑같은 방식인데 TypeError를 겪으며 문제를 자꾸 틀렸다. 그래서 Python으로 똑같은 코드를 구현했는데 바로 맞았다고 해서 어이가 없었다. 마음이 아프다.