백준 13023 ABCDE

문제

---

솔루션

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)

N,M = map(int,input().split())
A = [[] for _ in range(N+1)]
visited = [False] * (N+1)
arrive= False

def DFS(now,depth):
    global arrive
    if depth ==5:
        arrive=True
        return
    visited[now]=True
    for i in A[now]:
        if not visited[i]:
            DFS(i,depth+1)
    visited[now]=False

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

for i in range(N):
    DFS(i,1)
    if arrive:
        break
        
if arrive:
    print(1)
else:
    print(0)

---

깨달은 점

저번 DFS들과 비교했을때는 제일 어려운 느낌이였다.

감을 익힐라고 하나씩 풀어보는 중이다.

N, M = map(int, input().split())
A = [[] for _ in range(N + 1)]
visited = [False] * (N + 1)
arrive = False

 

• N은 노드(정점)의 개수, M은 간선의 개수.
• A 는 각 노드의 인접 노드를 저장하는 인접 리스트
• visited는 방문 여부 확인 위한 리스트
• arrive는 깊이 5인 경로를 찾았는지 여부를 나타내는 변수 

def DFS(now, depth):
    global arrive
    if depth == 5:
        arrive = True
        return
    visited[now] = True
    for i in A[now]:
        if not visited[i]:
            DFS(i, depth + 1)
    visited[now] = False

 

현재 노드에서 시작하여 깊이가 5가 되는 경로가 존재하는지 확인하는 DFS 함수

 

• if depth == 5: 현재 경로의 깊이가 5에 도달하면 arrive를 True로 설정하고 함수 종료
• visited[now] = True: 현재 노드를 방문한 것으로 표시
• for i in A[now]: 현재 노드 now에 연결된 모든 인접 노드를 순회
  • if not visited[i]: 인접 노드 중 방문하지 않은 노드가 있으면 그 노드로 이동하며, depth를 1 증가시키고 DFS를 호출
• visited[now] = False: 재귀 호출이 끝나면 백트래킹을 위해 현재 노드를 방문하지 않은 상태로 되돌림-> 다른 경로 탐색을 위해 사용

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

 

각 노드 a와 b를 서로의 인접 리스트에 추가하여 무방향 그래프의 간선을 저장

for i in range(N):
    DFS(i, 1)
    if arrive:
        break

 

• DFS(i, 1): 노드 i에서 깊이 1부터 DFS 시작
• if arrive: break: 깊이 5의 경로를 찾으면 더 이상 탐색을 진행할 필요가 없으므로 for 루프를 종료