개발자
안녕하세요! 백준 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)
답변 2
인기 답변
작성자님의 코드는 백준 1240번 같은 문제에서는 적용이 가능합니다. 같은 노드를 재방문할 일이 없거든요. 그러나 같은 노드를 재방문해야할 필요가 있을 때, 작성자님의 코드는 재방문이 불가능해집니다. 특히 트리나 그래프에서 두 갈래 길 이상으로 나뉘어지고, 다시 합쳐지는 경로가 있을 때 문제가 발생합니다. 예를 들어 다음과 같은 노드가 있고, 주어진 대로 연결되어있다고 가정하겠습니다. 노드 1 노드 2 노드 6 노드 3 노드 4 노드 5 Graph[1] = 2, 6 Graph[2] = 1, 3 Graph[3] = 2, 4, 5, 6 Graph[4] = 3 Graph[5] = 3 Graph[6] = 1, 3 작성자님의 코드에 따르면 노드 1 -> 노드 2 -> 노드 3 -> 노드 4 -> 노드5 여기까지는 정상 탐색입니다. 하지만 노드 6에서 문제가 발생합니다. 노드 1 -> 노드 6 DFS 개념대로라면 노드3, 노드 4, 노드 5 까지 방문해야합니다. 하지만 visit이 이미 true기 때문에 방문이 불가능해집니다. 노드 2에서의 DFS가 노드 6의 DFS에 영향을 끼치고 있는 상태입니다. 이렇듯 서로 다른 경로의 DFS끼리 영향을 주지 않기 위해서, 탐색이 끝나면 visit을 false 처리해주는 겁니다. * 그리고 문제에서는 전역 변수를 사용하셨습니다. 백준 1240번 풀어보시면서 전역 변수 dfs랑 지역 변수 dfs 차이도 한 번 테스트 해보세요!
이지헌
작성자
삼성청년SW아카데미(SSAFY) 웹 개발 • 2024년 01월 10일
정말 자세하게 예시까지 들어주셔서 수월하게 이해했습니다. 덕분에 제 부족한 구멍을 메꾼 것 같아요! 정말 감사합니다. 좋은 하루 보내세요
삭제된 사용자
2024년 01월 10일
해당 문제는 단순히 DFS를 적용하는 문제는 아닙니다. 이 문제는 사실상 그래프에서 발생하는 모든 단순 경로(정점과 간선이 중복되지 않는 경로)를 탐색하고 그 중에서 정점의 개수가 5인 단순 경로가 존재하는지 찾는 문제입니다. 즉, 모든 경로를 탐색해야 하는 문제이며 효과적으로 풀기위해 DFS와 유사한 솔루션을 택했을 뿐입니다. 그러므로 DFS의 재귀 반복 이후, visited를 해제해줘야 합니다. 일반적인 DFS는 한번 방문한 정점은 다시 방문하지 않기 때문입니다. 학창시절 수학시간 중 경우의 수에서 배운 나무와 가지 그림을 생각하시면 쉬우실 것 같습니다. (이 사이트가 설명이 잘 되어있는 것 같으니 참고하시길 바랍니다. https://loosie.tistory.com/m/509) 다만, 간선의 수가 2000개이므로 모든 경우의 수를 단순히 계산하면 2000*1999*1998*1997번의 경우의 수가 발생합니다(우리는 간선의 개수가 4개면 충분하기 때문입니다). 그러므로 DFS를 이용하여 2000*(평균 차수)^4의 연산 안에 수행하도록 푸는 문제입니다.
이지헌
작성자
삼성청년SW아카데미(SSAFY) 웹 개발 • 2024년 01월 10일
답변 정말 감사합니다. DFS의 개념에 대해 살짝 혼동이 있었던 부분을 찾아낸 것 같습니다 덕분에! 좋은 하루 보내세요
익명
작성자
2024년 01월 10일
도움이 되셨다니 다행이네요. 해당 문제를 이해하실 때는 dfs라는 단어에 매몰되지 않는 것이 중요할 것 같습니다.
이지헌
작성자
삼성청년SW아카데미(SSAFY) 웹 개발 • 2024년 01월 10일
넵 명심하도록 하겠습니다!
지금 가입하면 모든 질문의 답변을 볼 수 있어요!
현직자들의 명쾌한 답변을 얻을 수 있어요.
이미 회원이신가요?
커리어리 AI 봇
GPT가 달아주는 답변입니다.
2024년 01월 09일
두 코드 사이의 주요 차이점은 언제 visited array를 업데이트하느냐와 관련이 있습니다. **틀린 코드:** 여기서는 DFS가 호출 될 때마다 해당 노드를 방문한 것으로 체크합니다. ```python visited[x] = True ``` 이 방법의 문제점은, 그래프에서 다른 경로를 통해 동일한 노드에 다시 도달할 경우, 이미 '방문함'으로 표시되어 있기 때문에 그 경로를 추적하지 않게 되는 것입니다. 이는 일부 그래프 탐색 문제에서는 올바른 접근법일 수 있지만, 이 문제에서는 정확한 결과를 내지 못합니다. **정답 코드:** 반면에 정답 코드에서는 각 경로를 완전히 탐색하고 나서야 해당 노드의 '방문함' 상태를 해제합니다. ```python visited[i] = True dfs(i, level + 1) visited[i] = False ``` 이렇게 하면 같은 노드를 여러 번 방문할 수 있고, 따라서 가능한 모든 경로를 탐색할 수 있습니다. 이 문제에서는 네트워크의 모든 가장 긴 연결 요소(즉, 친구 관계에 의해 직간접적으로 연결된 집합)을 찾아야 하므로, 이 접근법이 맞습니다. 따라서, '어떤 노드를 다시 방문할 수 있느냐'와 '모든 가능한 경로를 탐색해야 하는가'에 따라 두 코드 사이에서 선택해야 합니다.
지금 가입하면 모든 질문의 답변을 볼 수 있어요!