그래프 탐색을 파이썬으로 해봤당
adjList = {}
N, M, V = map(int, input().split())
for i in range(1, N+1):
adjList[i] = []
for i in range(M):
s, e = map(int, input().split())
adjList[s].append(e)
adjList[e].append(s)
dfs(V)
print()
bfs(V)입력받고, 깊이우선탐색 결과 출력하고, 너비우선탐색 결과 출력하면 끝이다.
원래 dfs를 항상 재귀로 구현했었는데 이번에는 스택으로 구현해봤다.
def dfs(s):
visit = list()
stack = list()
stack.append(s)
while stack:
curr = stack.pop()
if curr not in visit:
print(curr, end=' ')
visit.append(curr)
for e in sorted(adjList[curr], reverse=True):
# 큰 수부터 쌓아야 작은 수가 먼저 탐색되므로 역순으로 검사
if e not in visit:
stack.append(e)
근데 ^^... 실수를 했던 게 노드가 스택에 쌓은 반대 순서로 탐색된다는 당연한 사실을 잊고 for문을 작은 수부터 돌려서 계속 순회 결과가 이상하게 나왔었다. reverse 조건 다니까 맞았다. 재귀와 스택은 LIFO입니다 이런 실수를 하다니
너비우선탐색은 파이썬으로는 처음으로 해본 것 같다 짱좋다 파이썬. 리스트로 해도 아무 상관 없다. pop() 메서드의 파라미터로 원하는 인덱스를 지정하면 앞에 있는 애를 뽑아올 수 있다.
def bfs(s):
visit = list()
queue = list()
queue.append(s)
while queue:
curr = queue.pop(0)
if curr not in visit:
visit.append(curr)
print(curr, end=' ')
for e in sorted(adjList[curr]):
if e not in visit:
queue.append(e)근데 다른 사람들의 풀이를 보면 deque을 많이 사용하더라. 덱은 스택과 큐가 합쳐진 자료형으로, 처음과 마지막에서 모두 출입이 가능하다.
다른 사람들은 대체로 리스트보다는 덱을 이용해서 문제를 풀었다. 내 코드를 덱으로 수정해보자면,
from collections import deque
# ...
def bfs(s):
visit = list()
queue = deque()
queue.append(s)
while queue:
curr = queue.popleft()
if curr not in visit:
visit.append(curr)
print(curr, end=' ')
for e in sorted(adjList[curr]):
if e not in visit:
queue.append(e)음 딱히 다를 건 없는 것 같아 보인다.
