////
Search
✏️

DFS와 BFS

문제 설명
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... 노드들은 아래의 관계에 있다고 가정하고 예시를 설명하는 것이다. (AB), (AC), (AD), ... (B→?), (C→?)
재귀 함수를 사용하여 구현하였으며, 큰 순서는 아래와 같다.
1.
함수 실행 시 노드는 방문상태로 변경 (visit의 해당 노드 값을 key로 가지는 값 변경 & 노드 값 출력)
2.
함수 실행 노드(A)연결된 노드(B)가 방문하지 않은 상태일 때, 연결된 노드(B)로 dfs 함수 실행
즉 (AB) 연결 관계를 발견하였고, 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... 노드들은 아래의 관계에 있다고 가정하고 예시를 설명하는 것이다. (AB), (AC), (AD), ... (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에서 사용하던 graphvisit 을 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
복사