[백준] 13023번 ABCDE - 파이썬/DFS

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

import sys
sys.setrecursionlimit(10**6)

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

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

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


def dfs(x,visited,cnt):

    global answer

    if cnt == 4:
        answer = 1
        return

    visited[x] = True

    for i in graph[x]:
        if not visited[i]:

            dfs(i,visited,cnt+1)

    visited[x] = False


for i in range(N):
    answer = 0

    visited = [False for _ in range(N)]
    dfs(i,visited,0)
    if answer == 1:
        print(answer)
        break

else:
    print(0)

문제가 살짝 이해하기 힘들지만 요약하자면 한점에서 출발하여 5번째 요소까지 방문할 수 있냐를 묻는 문제이다.

즉,

A-B
A-C
A-D
A-E

이런 그래프는 문제 조건을 만족시킬 수 없다.

DFS 문제지만 백트래킹 개념이 필요하다.

탐색이 실패한 루트에 대해서 방문 취소를 해줘야한다.

각 점에서 DFS를 수행해주고 조건에 맞는 루트가 나올때 1을 출력, 맞는 루트가 하나도 없을때 0을 출력했다.