[BOJ]13023 ABCDE

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

13023번: ABCDE

[출처 BOJ]

문제

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을 출력한다.

풀이

모든 사람들에 대하여 순차적으로 5명의 연이은 친구들이 있는지 탐색하면 되는 문제다. 깊이 우선 탐색으로 풀면 시간적인 측면에서 유리할 거 같아서 재귀를 이용하여 풀어보았다. 이 문제의 중점은 방문 처리였던 것 같다. 일반적인 방문처리와 다르게 이 문제에서는 한 사람에 대한 재귀가 완료되면 방문처리를 False로 바꿔줘야 한다. 예로 들면 4-3-2로 재귀를 해줄 때 3은 1과 연결이 되어있다면, 4 3 2에서 4 3 1로 갈 때 2는 방문처리가 되지 않은 상태여야 한다. 왜냐하면 둘은 독립된 사건이기 때문이다. 이 점만 해결하면 다른 DFS문제와 다르지 않다.

import sys
input = lambda: sys.stdin.readline().rstrip()
n, m = map(int, input().split())
friend = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    friend[a].append(b)
    friend[b].append(a)
visited = [False for _ in range(n)]
flag = False
def dfs(x, cnt):
    global flag
    visited[x] = True
    for i in friend[x]:
        if not visited[i]:
            if cnt == 3:
                flag = True
                return
            dfs(i,cnt+1)
    visited[x] = False
for i in range(n):
    dfs(i, 0)
    if flag:
        break
if flag:
    print(1)
else:
    print(0)