그래프에 대해 공부하기 시작할 때, 가장 먼저 짚고 갈 내용은
BFS(너비우선탐색) 와 DFS(깊이우선탐색)일 것이다.
가장 보편적이고 다양하게 사용되는 알고리즘들 중 하나이기 때문이다.
BFS, DFS에 대한 설명을 어떻게든 해보려고 교재도 뒤져보고 공부했던 파일들을
꽤 찾아봤지만 할 말이 명쾌하게 떠오르지 않아서 나보다 뛰어나신 수많은 인터넷 선배님들께 맡기기로 했다..
최대한 간략히 말하자면 BFS는 root노드에서 인접한 노드를 먼저 방문하고 멀리있는 노드는 나중에 방문하는 방식으로 흔히 넓게 탐색한다고 말한다.
이 과정에서 큐라는 선입선출 방식의 자료구조를 사용하여 구현하는 것이 보편적이다.
DFS는 하나의 Branch를 완벽히 탐색한 후 다음 Branch를 탐색하는 방식으로 흔히 깊게 탐색한다고 말한다. 흔히 재귀함수를 통해 구현하며 스택이라는 후입선출 방식의 자료구조를 사용하여 구현하기도 한다.
위 두 가지 탐색방식에서 공통적으로 중요한 것은 방문한 노드와 방문하지 않은 노드를 구분하는 것이다. 그렇지 않으면 무한루트에 빠지거나 올바른 탐색이 이뤄지지 않을 수 있다.
추가로, 그래프 탐색을 구현할 때 가장 기초는 노드와 간선을 표현하는 것이다. 이 때, 인접 리스트 혹은 인접 행렬을 통해 표현하게 되는데 나의 경우에는 아직까진 인접행렬 방식으로 구현하는 것이 편한 것 같다.
지금까지 말한 것을 바탕으로 1260번 문제에 대해 정리해보자면 다음과 같다.
BFS(V)
큐에 V 삽입
노드V 방문 표시
큐가 비어있지 않을 동안 반복 :
1. 큐에서 노드를 하나 꺼냄
2. 꺼낸 노드의 번호 출력
3. 노드에서 연결되어 있는 노드들 중 아직 방문하지 않은 노드들을
큐에 삽입하고 방문 표시
DFS(V)
노드V 방문 표시
의 번호 출력
모든 노드에 대해 반복 :
V에 연결되어 있는 노드 중 아직 방문하지 않은 노드 X에 대해
DFS(X)를 재귀호출
코드는 다음과 같다.
import sys
from collections import deque
input = sys.stdin.readline
N, M, V = map(int,input().split())
graph = [[0 for i in range(N)] for i in range(N)]
visited_BFS = [False] * N
visited_DFS = [False] * N
def DFS(V):
global visited_DFS
visited_DFS[V] = True
print(V + 1, end = ' ')
for i in range(N):
if graph[V][i] == 1 and not visited_DFS[i] :
DFS(i)
def BFS(V):
global visited_BFS
que = deque()
que.append(V)
visited_BFS[V] = True
while(que):
tmp = que.popleft()
print(tmp + 1,end = ' ')
for i in range(N):
if graph[tmp][i] == 1 and not visited_BFS[i] :
que.append(i)
visited_BFS[i] = 1
visited_BFS = [False] * N
for i in range(M):
S,E = map(int,input().split())
graph[S - 1][E - 1] = 1
graph[E - 1][S - 1] = 1
DFS(V - 1)
print()
BFS(V - 1)N x N 사이즈로 행렬을 선언해서 함수를 호출할 때 V가 아닌 V - 1을 인자로
하는 것 이외에는 특별히 다른 내용은 없는 것 같다. 그런데 graph[ ][ ]는 global 처리를 해주지 않아도 괜찮은데 visited[ ]는 global처리를 해줘야하는 이유를 아직 잘 모르겠는데 공부를 해봐야 할 것 같다.
종합 평가
시간 복잡도 :
소요 시간 : 20 ~ 30분
실패 횟수 : 1, 출력초과 (테스트용 출력문을 안 지움)
