백준 13023 : ABCDE (Python)

본문 링크

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M = map(int, input().split())

graph = [[] * N for i in range(N)]

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


answer=0
def DFS(a,count):
    global answer
    visit[a] = True
    if count>=5:
        print(1)
        exit(0)
        
    for i in graph[a]:
        if not visit[i]:
            visit[i] = True
            DFS(i,count+1)
            visit[i]=False


for i in range(N-1):
    visit = [False] * N
    DFS(i,1)

print(0)

📌 어떻게 접근할 것인가?

전형적인 $DFS$ 문제이다.
문제를 읽다가 처음에는 모든 친구들이 서로 연결되어있어야 하는 줄 알았다.
알고보니 5명 이상만 서로 연결되어있으면 된다.

$DFS$ 매개변수에 count 변수를 만들어서 얼마나 깊이 탐색해주었는지 확인해준다.
만약 5명이상이라면 1을 출력하고 바로 코드를 종료해준다.
하지만 처음에는 $DFS$ 탐색이후에 visit[i]를 다시 False 로 고치는게 이해가 되진않았다.

📌 왜 방문처리를 다시 지워주어야하는가?

질문게시판
다행히 누군가가 3년전에 잘 설명을 해주었다.

• 5 5
  1 2
  2 4
  2 3
  3 4
  4 5

이때 먼저 1-2-4-5를 탐색해버리면 방문처리가 되므로 1-2-3-4-5를 탐색하지 못하게된다.
따라서 백트래킹 기법을 사용해야한다.