백준 1260번 - DFS와 BFS

백준 1260 - DFS와 BFS

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오.

DFS와 BFS의 개념은 알고 있었다. 깊이 우선 탐색과 너비 우선 탐색. 근데 문제를 풀려니까 이걸 어떻게 적용시켜야 하는지 이해가 되지 않았다. 천천히 파헤쳐보자.

먼저 DFS나 BFS를 언제 사용하는지 생각해보자. 길찾기나 미로 등 선택지가 많을 때 사용한다고 할 수 있다. 그 선택지들을 하나를 물고 늘어뜨릴 것인지, 여러가지를 두루두루 해볼 것인지를 결정하면 된다.
방식은 똑같고 방문 순서만 다르다. 여러가지 선택지를 가보고, 가봤는지 표시하고, 각각의 이론에 맞게 하나씩 방문해보면 된다.

요약하면,

1. graph 만들기
2. DFS or BFS 코드 짜기
3. 출력 형태 맞추기

from sys import stdin
from collections import deque

input = stdin.readline

# dfs로 방문
def dfs(graph, v):
  visited = {}
  stack = [v]
  while stack:
    n = stack.pop()
    if n not in visited:
      visited.setdefault(n, 1)
      stack += reversed(graph[n])
  return visited


# bfs로 방문
def bfs(graph, v):
  visited = {}
  queue = deque([v])
  while queue:
    n = queue.popleft()
    if n not in visited: 
      visited.setdefault(n, 1)
      queue += graph[n]

  return visited

# graph 형성
n, m, v = map(int, input().split())
graph = {i:[] for i in range(1,n+1)}

for i in range(m):
  x, y = map(int, input().split())
  graph[x].append(y) 
  graph[y].append(x) # 양방향 

for key in graph:
  graph[key].sort() # 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문.

print(' '.join(list(map(str,dfs(graph, v)))))
print(' '.join(list(map(str,bfs(graph, v)))))