백준 1260번: DFS와 BFS

✔ 풀이를 위한 아이디어

• 그래프 (Graph) 이론
• 깊이 우선 탐색 (DFS) 과 너비 우선 탐색 (BFS)
  
  

✔ 코드

import sys
from collections import deque

N, M, V = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(N+1)]

for _ in range(M):
    A, B = map(int, sys.stdin.readline().split())
    graph[A].append(B)
    graph[B].append(A)

#DFS
visited = []
stack = [V]

while stack:
    tmp = stack.pop()
    if tmp not in visited:
        visited.append(tmp)
        plus = list(set(graph[tmp]) - set(visited))
        plus.sort(reverse=True)
        stack += plus
        
for i in range(len(visited)):
    print("{} ".format(visited[i]), end="")
print()

#BFS
visited = []
queue = deque([V])

while queue:
    tmp = queue.popleft()
    if tmp not in visited:
        visited.append(tmp)
        plus = list(set(graph[tmp]) - set(visited))
        plus.sort()
        queue += plus
        
for i in range(len(visited)):
    print("{} ".format(visited[i]), end="")
print()

• 연산의 최소화를 위해 덱(Deque) 모듈을 사용하였다.
• 깊이 우선 탐색 (DFS) 는 스택 (Stack) 을 활용하고, 너비 우선 탐색 (BFS) 는 큐 (Queue) 를 사용한다.
• 한가지 주의할 점은, 이 문제에서는 작은 수부터 출력하기를 원했기 때문에 스택에 넣어줄 때 내림차순으로 정렬을 해서 넣어주었다.
• 중복된 값을 제거하기 위해 집합 (Set) 도 사용하였다.

처음으로 풀어본 DFS, BFS 문제! 푸는 방식을 잘 익혀보자

✔ 관련 개념 (참고 링크)

• DFS와 BFS의 개념: https://devuna.tistory.com/32
• 참고한 Python 코드: https://cyc1am3n.github.io/2019/04/26/bfs_dfs_with_python.html
• 스택과 큐를 사용하는 이유 직관적인 그림 Ver: https://www.zerocho.com/category/Algorithm/post/5870153c37e1c80018b64eb0