[Python] 재귀를 이용한 2개의 DFS 코드 차이점을 모르겠습니다.

안녕하세요! 백준 13023번 - ABCDE 번을 파이썬으로 풀다가 이해가 되지 않는 부분이 있어서 조심스레 질문을 남깁니다. 위의 코드와 아래 코드의 차이는 visited와 dfs를 더 깊게 탈 때, 방문배열을 체크하고 해지하는 방식의 차이가 있습니다. 제가 생각하기에는 위의 코드가 dfs 함수에 들어가자마자 visited[x] =True 를 하니깐, 굳이 밑의 코드의 visited[i] = True dfs(i, level + 1) visited[i] = False 이 부분과 같이 할 필요가 없다고 생각했습니다. 하지만 위의 코드를 사용한 것은 오답이고, 아래 코드는 정답이라 둘의 코드의 차이가 있는지 궁금합니다. 제가 생각하기엔 두 코드가 동일하게 작동한다고 생각했습니다. 혹시 어떤 부분에서 차이가 있는지 알려주실 수 있을까요? 혹시나 해서 맨 밑에, 제가 제출했는데 틀린 코드를 적어놓겠습니다!

1# 오답 코드
2def dfs(x,level,visited) :
3    global answer
4    visited[x] = True
5    if level == 5 :
6        answer = 1
7        return
8    for i in graph[x] :
9        if not visited[i] :
10            dfs(i,level+1,visited)
11
12for i in range(v) :
13    visited = [False] * (v + 1)
14    dfs(i,1,visited)
15    if answer :
16        break
17
18# 정답 코드
19
20def dfs(x, level):
21    global answer
22    if level == 5:
23        answer = 1
24        return
25    for i in graph[x]:
26        if not visited[i]:
27            visited[i] = True
28            dfs(i, level + 1)
29            visited[i] = False
30
31for i in range(v):
32    visited = [False] * (v + 1)
33    visited[i] = True
34    dfs(i, 1)
35    if answer:
36        break
37
38
39
40##### 제출한 틀린 코드 #####
41import sys
42sys.setrecursionlimit(10**6)
43v,e = map(int,input().split())
44graph = [[] for _ in range(v+1)]
45for i in range(e) :
46    a,b = map(int,input().split())
47    graph[a].append(b)
48    graph[b].append(a)
49answer = 0
50def dfs(x,level,visited) :
51    global answer
52    visited[x] = True
53    if level == 5 :
54        answer = 1
55        return
56    for i in graph[x] :
57        if not visited[i] :
58            dfs(i,level+1,visited)
59
60for i in range(v) :
61    visited = [False] * (v + 1)
62    dfs(i,1,visited)
63    if answer :
64        break
65print(answer)

이 질문이 도움이 되었나요?

'추천해요' 버튼을 누르면 좋은 질문이 더 많은 사람에게 노출될 수 있어요. '보충이 필요해요' 버튼을 누르면 질문자에게 질문 내용 보충을 요청하는 알림이 가요.

추천해요 0

보충이 필요해요 0

이지헌 삼성청년SW아카데미(SSAFY) 웹 개발 님의 질문