백준 13023 ABCDE - 골드5 [파이썬]

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

13023번: ABCDE

 

그래프 복습.

이번 문제는 DFS를 이용하는 문제였다.

연결된 노드를 따라 건너면서 step이 4 이상이 되면 조건에 맞는다고 판단한다.

 

import sys
input = sys.stdin.readline
N, M = map(int, input().split(" "))
graph = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split(" "))
    graph[a].append(b)
    graph[b].append(a)

for i in range(N):
    graph[i].sort()

isEnd = False


def DFS(v, step, visited):
    # print("v = {}, step = {}, visited = {}".format(v, step, visited))
    global isEnd
    if isEnd == True:
        return
    if step >= 4:
        isEnd = True
        return

    for i in graph[v]:
        if visited[i] == False:
            visited[i] = True
            DFS(i, step+1, visited)
            visited[i] = False


for i in range(N):
    visited = [False for i in range(N)]
    visited[i] = True
    DFS(i, 0, visited)
    visited[i] = False
    if isEnd == True:
        break

print(0 if isEnd == False else 1)

백트랙킹이면 DFS함수 나올 때 visited[i] = False 해줘야하는데, 그거 까먹어서 1번 틀렸다,.