[백준] 1260번 DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

• 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

-첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

풀이

from collections import deque

n, m, v = map(int, input().split())

# 연결 여부 그래프 만들기 (양방향을 고려해서 제작)
graph = [[False] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
  a, b = map(int, input().split())
  graph[a][b] = True
  graph[b][a] = True
# 방문 여부 그래프 만들기
visited = [False] * (n + 1)


# dfs 함수 정의
def dfs(v):
  # 일단 방문하고 프린트
  visited[v] = True
  print(v, end=' ')
  # 모든 노드에 대해서 연결 여부를 확인해야 하므로, v 번째 연결 여부 그래프와 방문 여부를 확인함.
  for i in range(1, n + 1):
    # 만약 연결되어 있고, 방문되어 있지 않다면. dfs 실행
    if graph[v][i] and not visited[i]:
      dfs(i)


# bfs 함수 정의
def bfs(v):
  # 큐 구현, 미리 v 노드를 넣어놓음.
  queue = deque([v])
  # 큐에 넣었다면 방문했다고, 설정
  visited[v] = True
  while queue:
    # 큐에서 뺄 때, 프린트. 즉 방문하고 나옴.
    v = queue.popleft()
    print(v, end=' ')
    # dfs와 마찬가지로, 연결 여부 그래프와 방문 여부를 확인함.
    for i in range(1, n + 1):
      if (graph[v][i] and not visited[i]):
        queue.append(i)
        visited[i] = True


dfs(v)

# visited 초기화
visited = [False] * (n + 1)
print()
bfs(v)

후기

• 하도 오랜만에 dfs와 bfs 코드를 다시 써보는 거라서 어려운 점이 많았다. 무엇보다 c언어로 구현했던 것을 python으로 구현하려고 하니, 인터넷을 찾아보면서 코드를 분석하면서 어려움이 많았다. 그래도 이번에 원리를 이해했으니, dfs와 bfs 문제를 다양하게 풀어볼 생각이다.

주의할 점

• 문제의 조건을 잘 확인하자.
• True와 false를 잘 구분하자.(사소한 실수를 조심하자.)