•
문제 설명
DFS와 BFS의 개념을 이해했는지 묻는 문제로, 공부할 때 예시처럼 탐색 결과를 출력하는 것 이다.
•
성공 코드
•
코드 설명
◦
입력 값 확인 부분
graph 변수에 양방향의 관계를 모두 추가한다.
예를 들어 5 2 로 값을 받아온다면, 해당 값은 5→2의 관계만 표현한 값이다. 이때 graph 변수에는 [5, 2] 값이 들어간다.
하지만 이의 역방향 관계, 즉 2→5의 대한 값은 설정하지 않았기 때문에 추가적으로 [2, 5] 값도 넣어주는 것이다.
코드에서는 visit 에서 방문 여부에 따라 출력하기 때문에 문제 될 것이 없다.
visit 값은 graph에 들어있는 값을 key로, value는 방문여부를 boolean 형태로 저장한다.
EX) { 1: False, 2: True ... } → 노드 값 1은 방문 X / 노드 값 2는 방문 O
...
# 정점 갯수
N, M, V = map(int, input().split())
# 그래프의 연결된 관계를 나타낸 배열
graph = []
# 각 노드의 간선으로 연결된 관계를 양방향으로 추가해준다.
for _ in range(M):
x, y = map(int, input().split())
graph.append([x, y])
graph.append([y, x])
# 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하기 때문에, 정렬을 해준다.
graph.sort(key=lambda x:[x[0], x[1]])
# 방문 여부를 각 노드의 값으로 확인하기 위해 dict 형태로 저장한다.
visit = {item: False for i in graph for item in i}
...
Python
복사
◦
dfs 함수 정의 부분
예시의 A노드와 B, C... 노드들은 아래의 관계에 있다고 가정하고 예시를 설명하는 것이다.
(A→B), (A→C), (A→D), ... (B→?), (C→?)
재귀 함수를 사용하여 구현하였으며, 큰 순서는 아래와 같다.
1.
함수 실행 시 노드는 방문상태로 변경 (visit의 해당 노드 값을 key로 가지는 값 변경 & 노드 값 출력)
2.
함수 실행 노드(A)와 연결된 노드(B)가 방문하지 않은 상태일 때, 연결된 노드(B)로 dfs 함수 실행
•
즉 (A → B) 연결 관계를 발견하였고, B가 방문하지 않은 상태라면 A와 연결된 다른 노드(C, D...)를 전부 확인하지 않고, B노드와 연결된 다른 노드들에 대한 먼저 탐색이 종료되면 A와 연결된 남은 노드의 탐색을 진행한다.
•
그렇기 때문에, A노드에 대한 for문이 끝나기 전에 재귀함수를 동작시키는 것이다.
# DFS 함수
def dfs(graph, v, visit):
# 저장여부를 저장하는 visit에서 방문 노드의 값을 True로 설정
visit[v] = True
# 방문한 노드 값 출력
print(v, end=' ')
# 그래프의 연결된 관계 확인
for item in graph:
# 최상단 노드는 확인하지 않는다.
if item == []: continue
else:
for i in item:
# 만약 방문한 노드와 연결된 노드가 방문하지 않은 상태일 때
# dfs 함수를 동작하기전에 낮은 값의 노드를 우선으로 가져오도록 정렬하였다.
# 노드 방문 순서는 걱정하지 않아도 된다.
if v in item and visit[i] != True:
# 해당 노드를 바로 방문하여 연결된 노드가 존재하는지 확인
# 재귀 함수 동작
dfs(graph, i, visit)
Python
복사
◦
bfs 함수 정의 부분
예시의 A노드와 B, C... 노드들은 아래의 관계에 있다고 가정하고 예시를 설명하는 것이다.
(A→B), (A→C), (A→D), ... (B→?), (C→?)
큐(deque)와 while문을 사용하여 구현하였으며, 큰 순서는 아래와 같다.
1.
우선 재귀 함수가 아니기 때문에, bfs() 함수는 1번 동작한다.
그래서 시작 부분에 최초 실행 노드가 초기로 삽입된 상태의 큐를 생성한다.
2.
DFS와 마찬가지로 함수 실행 시 노드는 방문상태로 변경 (visit의 해당 노드 값을 key로 가지는 값 변경 & 노드 값 출력)
3.
while문이 한번 반복될 때마다 하나의 노드(A)와 연결된 다른 노드(B, C, ...) 들을 모두 확인한다.
•
DFS는 하나의 노드(A)를 모두 확인하기 전, 조건에 맞는 노드(B) 발견 시 연결된 다른 노드(C, D...)를 확인하지 않고, 바로 탐색 노드를 변경하는 것(B가 A의 역할을 함)이 DFS와 BFS의 대표적인 차이점이다.
4.
만약 하나의 노드(A)와 연결된 다른 노드(B, C ...) 중 조건에 맞는 노드를 발견했다면, 조건에 맞는 노드의 방문 여부를 True로 변경하고, 값을 출력한다.
5.
4번 과정을 통해 방문여부가 수정되었다면, 하나의 노드(A) 탐색이 끝난 후 다음 탐색 순서가 되기 위해 큐(대기열)에 삽입된다.
이제 A의 탐색이 끝나면, 큐에 삽입된 순서대로 B, C... 노드가 A의 역할을 하게 되며 B, C... 와 연결된 노드를 전부 파악하게 된다.
6.
이렇게 더 이상 파악할 노드가 존재하지 않는다면, 함수의 동작을 끝낸다.
from collections import deque
...
# BFS 함수
def bfs(graph, v, visit):
# 시작하는 노드가 들어간 큐를 생성한다.
queue = deque([v])
# 첫 방문 노드의 방문 여부를 True로 변경한다.
visit[v] = True
# 첫 방문한 노드를 출력한다.
print(v, end=' ')
# 큐가 빈 상태가 될 때까지 동작한다.
# 한 번 반복할 때 마다, 방문한 한 노드의 방문하지 않는 모든 노드가 큐에 삽입된다.
while queue:
# 큐에 가장 먼저 삽입된 노드 값을 출력한다.
# EX) 이전에 (3, 1) (3, 4) 관계에서 3을 확인한 후, 큐에 [1, 4] 가 들어갔다면
# 이후에는 1과 연결된 노드를 확인하기 위해 1을 꺼내어 확인한다.
v = queue.popleft()
for item in graph:
if item == []: continue
else:
i = item[1]
# 현재 노드와 연결되있으며, 방문하지 않는 노드일 때
if v == item[0] and visit[i] != True:
# 방문한 상태로 변경
visit[i] = True
# 해당 노드 출력
print(i, end=' ')
# 다음 while문 동작 시, 해당 노드와 연결된 다른 노드를 확인하기 위해 값 저장
# 큐에 순서대로 저장된다.
queue.append(i)
Python
복사
◦
함수 동작 부분
DFS에서 사용하던 graph 와 visit 을 BFS에서 사용하면, 방문 상태등이 변경된 값을 사용하기 때문에 동작에 문제가 발생할 것이다.
그래서 기본 값 graph , visit 을 이전에 생성해두고 copy.deepcopy() 를 사용하여 기본 값을 가져오는 방식을 사용하였다.
import copy
...
# dfs 함수에서 그래프 초기값을 새로운 변수에 가져온다.
dfs_graph = copy.deepcopy(graph)
# 최상단 노드 추가(배열은 0부터 시작하기 때문에)
dfs_graph.insert(0, [])
# dfs 함수에서 visit 여부를 저장하는 초기값을 새로운 변수에 가져온다.
dfs_visit = copy.deepcopy(visit)
# dfs 함수를 동작
dfs(dfs_graph, V, dfs_visit)
# 한 줄 띄우기
print("")
# bfs 함수에서 그래프 초기값을 새로운 변수에 가져온다.
bfs_graph = copy.deepcopy(graph)
# 최상단 노드 추가(배열은 0부터 시작하기 때문에)
bfs_graph.insert(0, [])
# bfs 함수에서 visit 여부를 저장하는 초기값을 새로운 변수에 가져온다.
bfs_visit = copy.deepcopy(visit)
# bfs 함수 동작
bfs(bfs_graph, V, bfs_visit)
Python
복사