📘[1260] DFS와 BFS

문제

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

예제 입력 1

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력 1

1 2 4 3
1 2 3 4

예제 입력 2

5 5 3
5 4
5 2
1 2
3 4
3 1

예제 출력 2

3 1 2 5 4
3 1 4 2 5

답안

import sys
from collections import deque
# sys.setrecursionlimit(10000)

def dfs(v, visited):
    if v in visited:
        return
    visited.append(v)
    print(v, end=' ')
    for i in sorted(graph[v]):
        if i not in visited:
            dfs(i, visited)

def bfs(v, visited):
    queue = deque([v])
    visited.append(v)
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in sorted(graph[v]):
            if i not in visited:
                visited.append(i)
                queue.append(i)

input = sys.stdin.readline

n, m, v = map(int, input().split())
graph = [[] for _ in range(n + 1)]
visited = []

# 인접리스트 만들기
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

dfs(v, visited)
visited = []
print()
bfs(v, visited)

풀이

DFS의 이해

먼저 DFS에 대한 이해가 필요함.

가장 깊이 내려간 다음, 갈 길이 없으면 이전 분기로 돌아와 옆 리프로 넘어가는 방식의 탐색.

def dfs(v, visited):
    if v in visited:
        return
    visited.append(v)
    print(v, end=' ')
    for i in sorted(graph[v]):
        if i not in visited:
            dfs(i, visited)

visited라는 방문 기록을 남기는 리스트가 필요하고, 현재 탐색 중인 노드인 v(vertex), 그리고 v의 리프 노드에 해당하는 graph가 필요함.

위 코드를 아래처럼 바꿀 수도 있음.

def dfs(v, visited, graph):
    if v in visited:
        return
    visited.append(v)
    print(v, end=' ')
    for i in sorted(graph[v]):
        if i not in visited:
            dfs(i, visited, graph)

결국 같은 동작인데, graph만 인자로 주냐 마냐의 차이.

동작 순서는 아래와 같음.

1. v를 기준으로 탐색 시작
2. v가 방문기록(visited)에 있으면 return
3. 없으면 방문기록에 추가한 후 현재 탐색 중인 노드 출력
4. 문제에서 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고 라는 조건이 있기 때문에 v에 대한 리프 노드인 graph[v]를 정렬
5. 이후 graph를 순회하며 리프 노드 별로 방문 기록에 있는지 확인
6. 방문 기록에 없으면 탐색을 다시 해야하니까 재귀(DFS 시작)

BFS의 이해

BFS는 넓이 우선 탐색으로, 바로 아래 리프의 전부를 탐색하고 다음 리프로 넘어가는 탐색 방법.

즉, 최대한 넓게 이동한 다음 더 이상 이동할 수 없을 때 다음으로 넘어감.

def bfs(v, visited):
    queue = deque([v])
    visited.append(v)
    while queue:
        node = queue.popleft()
        print(node, end=' ')
        for i in sorted(graph[node]):
            if i not in visited:
                visited.append(i)
                queue.append(i)

DFS와 마찬가지로 graph를 인자로 줄 수도 있음.

BFS의 큰 특징 중 하나는 Queue를 사용한다는 것!

queue를 사용하기 위해 python의 deque를 사용하여 정의함.

• queue = deque([v])
• deque([v])를 함으로써, 탐색 중인 노드를 queue의 첫 번째 인자로 저장
• 큐를 정의하고, queue.append(v) 로 할 수도 있음.

이후, 현재 탐색 중인 노드를 방문 기록에 추가하고, BFS의 본격적인 탐색 시작.

DFS와 마찬가지의 이유로 sort를 해주고 리프 노드 탐색.

queue.append(i)는 queue에 인자를 추가함으로써 다시 탐색을 진행하기 위한 방법.

이게 사실상 BFS의 핵심일 수도..?

BFS의 동작 순서는 다음과 같음.

1. 큐 정의
2. 큐에 v 추가
3. v를 방문기록에 추가
4. 큐가 존재하지 않을 때까지 반복
5. 큐의 가장 첫 번째에 위치한 값을 pop하여 node에 저장 (탐색하려는 노드)
6. 출력하고
7. node에 대한 리프 노드 탐색 시작
8. 리프 노드 순회하면서 방문기록에 없으면?
9. 방문기록에 추가하고
10. 다시 그 노드를 큐에 저장

인접리스트의 이해

인접리스트는 노드(node)의 수가 많고, 간선(edge)의 개수가 적을 때 유용함.

무방향 그래프(양방향 그래프)일 경우 보통 아래와 같이 구현함.

# 무방향 그래프 예시
1 — 2
|  /
3

node, edge = map(int, input().split())

graph = [[] for _ in range(node)]

for _ in range(edge):
		start_node, end_node = map(int, input().split())
		graph[start_node].append(end_node)
		graph[end_node].append(start_node)

그럼 인접행렬은 무엇일까?

인접행렬은 노드의 수에 비해 간선의 수가 많을 때 유용함.

2차원 배열로 그래프를 표현하는 방법으로, 노드 i에서 j로 가는 간선이 있으면 1, 없으면 0으로 함.

무방향 그래프(양방향 그래프)일 경우 보통 아래와 같이 구현함.

node, edge = map(int, input().split())
graph = [[] for j in range(node) for i in range(node)]

for _ in range(edge):
		start_node, end_node = map(int, input().split())
		graph[start_node][end_node] = 1
		graph[end_node][start_node] = 1
	

# 인접행렬에서 ngod m열의 정보가 주어질 경우		
row, column, edge = map(int, input().split())
graph = [[] for j in range(column) for i in range(row)]

for _ in range(edge):
		start_node, end_node = map(int, input().split())
		graph[start_node][end_node] = 1
		graph[end_node][start_node] = 1

위에서는 전부 무방향 그래프에서만을 가정했을 때 결과임.

그럼 방향이 있는 그래프에서는?

인접행렬먼저 보자.

예를 들어 i → j로 가는 간선이 있으면 1로 하고, 무방향과 다르게 matrix[a][b] = 1만 해주고, matrix[b][a]는 값을 주지 않는다.

즉, matrix[1][2] = 1은 1 → 2 가 존재한다는 의미임.

matrix = [[0] * (n+1) for _ in range(n+1)]
edges = [(1,2), (1,3), (2,3)]

for a, b in edges:
		matrix[a][b] = 1
		
for row in matrix:
		print(row)

인접리스트는 각 노드에서 나가는 간선만 기록한다.

1: [2, 3]
2: [3]
3: []

n = 3
graph = [[] for _ in range(n+1)]
edges = [(1,2), (1,3), (2,3)]

for a, b in edges:
    graph[a].append(b)   # 방향 그래프니까 한쪽만 저장

결국 그래프의 방향성 차이는 다음과 같음.

1. 인접행렬
   • graph[a][b] = 1, graph[b][a] = 1 → 이게 무방향일 때.
   • graph[a][b] = 1 → 이게 방향 그래프일 때. (반대 간선 방향으로 값을 주는 로직 제거)
2. 인접리스트
   • graph[a].append(b), graph[b].append(a) → 이게 무방향일 때.
   • graph[a].append(b) → 이게 방향 그래프 일 때. (반대 간선 방향으로 값을 주는 로직 제거)

회고

• DFS의 동작 원리 이해하기
• BFS의 동작 원리 이해하기
• 인접 리스트는 어떻게 구현하지?
• 인접 리스트와 인접 행렬의 차이?
• 그래프의 방향성 유무에 따른 인접 행렬과 인접 리스트?