[알고리즘] 백준 13023 'ABCDE' 풀이 _ 파이썬

백준 13023 ABCDE
https://www.acmicpc.net/problem/13023
난이도 : 골드 5
유형 : DFS

풀이

문제에서 주어진 조건
A-B, B-C, C-D, D-E 와 같은 친구 관계가 주어지는 지 검사하는 문제이다.
줄줄이 계속 이어지는 친구 관계를 보고 DFS 문제임을 알아차려야했다.
(나는 알아차리지 못해서 백준 문제 유형이 DFS인 것을 보고 풀었다... )

DFS임을 깨닫고 나면 꽤나 간단했던 문제

일단 입력에서 주어지는 친구 관계를 딕셔너리 형태로 다 저장한 뒤,
DFS 함수를 짜서 친구 관계에 있는 애들을 재귀로 호출하면서 depth를 판단하는 방식으로 풀었다.
조건에서 A부터 E까지 4개의 관계가 연결지어서 일어나야하기 때문에 depth가 4가 되면 조건을 충족한 것으로 판단했다.

정답 코드

N, M = map(int, input().split())
dic = {x:[] for x in range(N)}
for _ in range(M):
    x, y = map(int, input().split())
    dic[x].append(y)
    dic[y].append(x)

#방문 여부 판단
visited = [False] * N

answer = 0

def dfs(nod, depth):
    global answer
    #depth가 4 = 조건 충족
    if depth == 4:
        answer = 1
        return
    #친구 관계인 애들 재귀 호출
    for x in dic[nod]:
        if visited[x] == False:
            visited[x] = True
            dfs(x, depth+1)
            visited[x] = False

#N명에 대해 시작 지점으로 다 돌아가면서 해보기
for i in range(N):
    #이미 조건 충족한 경우 break -> 안하면 시간초과
    if answer == 1:
        break
    visited[i] = True
    dfs(i, 0)
    visited[i] = False

print(answer)

이 코드로 약 3000ms의 시간 소요가 나왔는데 백준 사이트의 풀이 중에 같은 로직으로 1000ms 대의 시간이 나오는 코드들이 많이 있었다.
뭐가 다른 걸까...????