[python]백준 1260번: DFS와 BFS(DFS, BFS)

# 1260 DFS와 BFS

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

1260번: DFS와 BFS

코드

from collections import deque
N, M, V = map(int, input().split())

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

for i in range(M):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)
  graph[a].sort()
  graph[b].sort()

# DFS함수
def dfs(graph, V, visited):
  visited[V] = 1
  print(V, end=' ')
  for nx in graph[V]:
    if visited[nx] == 0:
      dfs(graph, nx, visited)

# BFS함수
def bfs(graph, V, visited):
  Q = deque([V])
  visited[V] = 1
  while Q:
    C = Q.popleft()
    print(C, end=' ')
    for nx in graph[C]:
      if visited[nx] == 0:
        Q.append(nx)
        visited[nx] = 1

visited = [0] * (N+1)
dfs(graph, V, visited)
print("")
visited = [0] * (N+1)
bfs(graph, V, visited)

📝 풀이

DFS(깊이우선탐색)와 BFS(너비우선탐색) 방식을 모두 사용해야 하는 문제이다.

 

DFS(Depth-First Search)는 깊이 우선 탐색으로, 탐색을 함에 있어서 보다 깊은 것을 우선적으로 하여 탐색하는 알고리즘이다. DFS는 맹목적으로 각 노드를 탐색할 때 주로 사용된다.

 

BFS(Breadth-First Search)란 너비 우선 탐색이라고도 불리며 그래프에서 시작 노드에 인접한 노드부터 탐색하는 알고리즘이다. BFS 알고리즘은 주로 그래프에서 모든 간선의 비용이 동일한 조건에서 최단 거리를 구하는 문제를 효과적으로 해결할 수 있는 알고리즘이다. 

 

DFS에서는 스택이 사용되고 BFS에서는 큐가 사용된다.

DFS와 BFS의 알고리즘 작동순서는 다음과 같다.

 

출처:https://velog.io/@wkdgus7113/%EA%B7%B8%EB%9E%98%ED%94%84%EC%99%80-DFS-BFS-%EC%A0%95%EB%A6%AC

DFS

1. 스택의 최상단 노드를 확인

2. 최상단 노드에서 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 뺀다.

 

BFS

1. 탐색 시작 노드 정보를 큐에 삽입하고 방문 처리한다.

2. 큐에서 노드를 꺼내 방문하지 않은 인접 노드 정보를 모두 큐에 삽입하고 방문 처리한다.

3. 2번의 과정을 더 이상 수행할 수 없을 때 까지 반복한다.

📝 코드 뜯어보기

from collections import deque
N, M, V = map(int, input().split())

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

BFS를 사용해야 하므로 from collections import deque를 통해 라이브러리를 import해주고, 주어진 정점의 개수를 N, 간선의 개수를 M, 탐색을 시작할 정점의 번호를 V에 저장해준다. 정점의 갯수 +1 만큼 그래프를 생성해준다. +1을 하는 이유는 11번 노드를 1로, 2번 노드를 2로 만들기 위함이다.

for i in range(M):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)
  graph[a].sort()
  graph[b].sort()
  
# sort 전 [[], [2, 3], [1, 5], [4, 1], [3, 5], [2, 4]]
# sort 후 [[], [2, 3], [1, 5], [1, 4], [3, 5], [2, 4]]

간선의 갯수만큼 반복문을 실행시켜주고 graph에 저장시켜준다. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것부터 방문해야 하므로 sort를 통해 정렬해준다.

# DFS함수
def dfs(graph, V, visited):
  visited[V] = 1
  print(V, end=' ') # 현재 노드 print
  for nx in graph[V]: # 현재 노드(V)와 연결된 다른 노드를 재귀적으로 방문
    if visited[nx] == 0: # 방문기록이 없다면
      dfs(graph, nx, visited) # 재귀 함수 실행

DFS 함수를 만들어준다. 문제에서 시작하는 V값을 줬기 때문에 visited[V] = 1을 시작코드에 적어준다. 그리고 반복문을 통해 현재 노드와 연결된 다른 노드를 방문하지 않았다면 재귀적으로 방문시켜 준다.

# BFS함수
def bfs(graph, V, visited):
  Q = deque([V])
  visited[V] = 1
  while Q:
    C = Q.popleft()
    print(C, end=' ')
    for nx in graph[C]:
      if visited[nx] == 0:
        Q.append(nx)
        visited[nx] = 1

BFS 함수는 다음과 같이 작성했다. Q = deque([V])로 현재 노드를 Q에 저장하고 초기 visited[V]를 방문처리 해준다. while Q를 통해 큐가 빌 때까지 계속해서 실행시킨다. Q.popleft()를 통해 원소를 출력해준다.

 

반복문을 통해 graph[C]를 순회하고 visited[nx]값이 방문되지 않은 곳이라면 Q에 nx값을 삽입시켜주면서 visited[nx]를 방문처리 해준다.

visited = [0] * (N+1)
dfs(graph, V, visited)
print("")
visited = [0] * (N+1)
bfs(graph, V, visited)

한 코드내에서 dfs와 bfs가 쓰이기 때문에 함수를 실행하기 전에 visited값을 초기화 해줘야 한다. dfs와 bfs함수 사이에 print("")를 넣어줘서 출력값을 구분시켜준다.