난이도

Gold 5

문제

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 4
0 1
1 2
2 3
3 4

예제 출력

1

해설 및 후기

처음에는 그러한 친구 관계가 만들어지는 경우의 개수를 구하는 문제인줄 알고 어렵게 풀었다. 그러나 문제를 다시 보니 그냥 그러한 관계가 있으면 1, 아니면 0을 출력하면 되는 것이었다. 따라서 dfs로 순회하면서 depth == 5인 경우에 바로 1을 출력하며 마친다.

같은 visit을 공유하더라도 어디서 접근했는지에 따라 depth가 다를 수 있으므로 visit을 계속 초기화하며 순회한다. 또한 예제로 미루어 보아 a-b의 관계 뿐만 아니라 b-a의 관계도 인정하므로 양방향 간선을 사용한다.

pypy로 제출해 겨우 시간초과를 면했다.

제출 코드

import sys
n,m = map(int, sys.stdin.readline().rstrip().split())

l = []
c = [[] for _ in range(n)]
for i in range(m):
    a,b = list(map(int,sys.stdin.readline().rstrip().split()))
    c[a].append(b)
    c[b].append(a)


def dfs(num,depth,visited):
    if(depth == 5):
        #print(visited)
        print(1)
        exit()
    for i in c[num]:
        if(not visited[i]):
            tmpv = visited[:]
            tmpv[i] = True
            dfs(i, depth+1, tmpv)

for i in range(n):
    vis = [False for _ in range(n)]
    vis[i] = True
    dfs(i,1,vis)

print(0)