[백준] 13023번 : ABCDE

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

13023번: ABCDE

깊이우선탐색(DFS)로 문제를 해결 하였습니다. 친구의 관계가 A->B->C->D->E와 같은 경우가 존재할경우, DFS탐색을 중지합니다.

사이클이 생기지 않도록 탐색한 친구는 또 탐색하지 않습니다.

Set 자료구조를 활용하여 깊이우선 탐색을 한 친구는 Set 자료구조에 추가하여 이미 방문한 친구를 찾을때 O(1) 시간복잡도로 찾을 수 있습니다.

 

import sys
sys.setrecursionlimit(100000)
N , M = map(int ,input().split())

graph = [[] for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    

def dfs(start):
    global isFriend
    if len(queue) == 5:
        isFriend = True
        return
    
    for friend in graph[start]:
        if friend not in queue:
            queue.add(friend)
            dfs(friend)
            queue.remove(friend)
            
queue = set()
isFriend = False
for i in range(N):
    queue.add(i)
    dfs(i)
    queue.remove(i)
    if isFriend:
        break

if isFriend:
    print(1)
else:
    print(0)