[백준] 13023번 ABCDE

💡문제접근

• DFS 탐색 알고리즘을 이용해 해결할 수 있는 문제였다. 모든 노드의 방문 여부를 체크하면서
  각각의 사람의 친구관계를 DFS를 이용해 탐색하면서 깊이를 1만큼 증가하여 깊이가 4에 도달한다면 A ~ E까지 모두 친구관계가 성립하므로 1을 출력하고 아니라면 0을 출력하는 방식으로 코드를 작성했다.

💡코드(메모리 : 34176KB, 시간 : 1832ms)

import sys
input = sys.stdin.readline
# 파이썬의 기본 재귀 깊이 제한은 1000으로 굉장히 적은 값을 가진다. 
# DFS 알고리즘을 이용해 문제를 풀 때는 재귀함수 제한을 반드시 크게 잡아야 recursionError가 발생하지 않는다.
sys.setrecursionlimit(10**6)

N, M = map(int, input().strip().split())
camp = [[] for _ in range(N)]
visited = [False] * N
flag = False
for _ in range(M):
    a, b = map(int, input().strip().split())
    camp[a].append(b)
    camp[b].append(a)

def DFS(v, depth):
    global flag
    visited[v] = True
    if depth == 5:
        flag = True
        return
    for i in camp[v]:
        if not visited[i]:
        	# 노드의 방문 여부를 True로 표시함(방문함)
            visited[i] = True
            DFS(i, depth + 1)
            # 노드의 방문 여부를 False로 표시함(방문 안함)
            visited[i] = False

for i in range(N):
    DFS(i, 1)
    # DFS 함수 내에 visited[v] = True가 있는 것을 볼 수 있다.
    # 시작 노드에서의 방문 여부를 False로 표시함(방문 안함)
    visited[i] = False
    # 만약 깊이가 5에 도달해서 flag가 True가 된다면 break
    if flag:
        break

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

💡소요시간 : 27m