[백준(BOJ)] 1260번 DFS와 BFS

문제

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

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

예시

Example 1:

Input: 4 5 1
	1 2
	1 3
	1 4
	2 4
	3 4
Output: 1 2 4 3
	1 2 3 4

 

Example 2:

Input: 5 5 3
	5 4
	5 2
	1 2
	3 4
	3 1
Output: 3 1 2 5 4
	3 1 4 2 5

 

Example 3:

Input: 1000 1 1000
	999 1000
Output: 1000 999
	1000 999

풀이

from collections import deque

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

graph = [[0] * (n + 1) for i in range(n + 1)]
# 방문 여부 나타내는 리스트
visited_dfs = [0] * (n + 1)
visited_bfs = [0] * (n + 1)

# 간선 정보 그래프에 표시
for i in range(m):
  a, b = map(int, input().split())
  graph[a][b] = graph[b][a] = 1

# 깊이 우선 탐색
def dfs(node):
  visited_dfs[node] = 1
  print(node, end=' ')

  for i in range(1, n+1):
    if(visited_dfs[i] == 0 and graph[node][i] == 1):
      dfs(i)

# 너비 우선 탐색
def bfs(node):
  q = deque([node])
  visited_bfs[node] = 1

  while q:
    node = q.popleft()
    print(node, end=' ')

    for i in range(1, n+1):
      if(visited_bfs[i] == 0 and graph[node][i] == 1):
        q.append(i)
        visited_bfs[i] = 1

dfs(v)
print()
bfs(v)

 

- dfs 함수는 재귀적으로 깊이 우선 탐색을 수행한다. 방문한 노드는 visited_dfs 배열을 통해 표시하고, 해당 노드를 출력한다. 이후 해당 노드와 연결된 아직 방문하지 않은 이웃 노드들에 대해 재귀적으로 탐색을 진행한다.

 

- bfs 함수는 큐를 활용하여 너비 우선 탐색을 수행한다. 큐에서 노드를 꺼내어 방문 처리하고 출력한 후, 해당 노드와 연결된 아직 방문하지 않은 이웃 노드들을 큐에 추가하고 방문 처리한다. 큐가 빌 때까지 이 과정을 반복한다.