DFS 알고리즘
-
DFS (Depth-First Search): 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
-
스택 자료구조(혹은 재귀 함수)를 이용
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 함
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리함, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
- 동작 예시
- 코드
# dfs 메서드 정의 def dfs(graph, v, visited): # 현재 노드를 방문 처리 visited[v] = True print(v, end='') # 현재 노드와 연결된 노드를 재귀적으로 방문 for i in graph[v]: if not visited[i]: dfs(graph, i, visited) # 각 노드가 연결된 정보를 표현 (2차원 리스트) # 노드는 1부터 시작하므로 인덱스 0 은 사용하지 않음 # 1번 노드는 2,3,8노드와 연결, 2번 노드는 1,7노드와 연결, 3번 노드는 1,4,5노드와 연결 ... graph = [ [], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ] # 각 노드가 방문된 정보를 표현 (1차원 리스트) visited = [False] * 9 # 정의된 DFS 함수 호출 dfs(graph, 1, visited)
BFS 알고리즘
-
BFS (Breadth-First Search): 너비 우선 탐색, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
-
큐 자료구조를 이용
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 함
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 넣고 방문 처리함
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
-
특정 조건에서의 최단 경로 문제를 해결하기 위한 목적으로 효과적으로 사용됨
-
동작 예시
- 시작 노드부터 가까운 노드를 우선적으로 탐색함 (거리가 1인 2,3,8 - 거리가 2인 7,4,5 - 거리가 3인 6)
-
코드
from collections import deque # BFS 메서드 정의 def bfs(graph, start, visited): # 큐 구현을 위해 deque 라이브러리 사용 queue = deque([start]) # 현재 노드를 방문 처리 visited[start] = True # 큐가 빌 때까지 반복 while queue: # 큐에서 하나의 원소를 뽑아 출력하기 v = queue.popleft() print(v, end='') # 아직 방문하지 않은 인접한 원소들을 큐에 삽입 for i in graph[v]: if not visited[i]: queue.append(i) visited[i] = True # 각 노드가 연결된 정보를 표현 (2차원 리스트) graph = [ [], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ] # 각 노드가 방문된 정보를 표현 (1차원 리스트) visited = [False] * 9 # 정의된 BFS 함수 호출 bfs(graph, 1, visited)
DFS & BFS 기초 문제 풀이
<문제> 음료수 얼려 먹기
-
문제 해결 아이디어
-
DFS 혹은 BFS로 해결
-
상화좌우로 연결된 것은 인접한 노드로 생각하여 그래프 형태로 모델링 가능
-
특정 지점에서 DFS/BFS를 실행해서 이동가능한 모든 경로에 대해서 방문처리를 진행하도록 처리
-
모든 노드의 지점에 대해서 DFS/BFS를 실행해서 방문처리가 이루어지는 지점에 대해서만 count를 수행하면 전체 연결요소가 몇 개인지 계산 가능
- 특정한 지점의 주변 상하좌우를 살펴본 뒤에 주변 지점 중 값이 ‘0’이면서 아직 방문하지 않음 지점이 있다면 해당 지점 방문
- 방문한 지점에서 다시 상하좌우를 살펴보며 방문을 진행하는 과정을 반복하면, 연결된 모든 지점을 방문할 수 있음
- 모든 노드에 대하여 1~2번의 과정을 반복하며, 방문하지 않은 지점의 수를 카운트
-
답안 예시
# DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문 def dfs(x,y): # 주어진 범위를 벗어나는 경우에는 즉시 종료 if x <= 1 or x >= n or y <= -1 or y >= m: return False # 현재 노드를 아직 방문하지 않았다면 if graph[x][y] == 0: # 해당 노드 방문 처리 graph[x][y] = 1 # 상하좌우 위치들도 모두 재귀적으로 호출 dfs(x-1, y) dfs(x, y-1) dfs(x+1, y) dfs(x, y+1) return True return False # N, M을 공백을 기준으로 구분하여 입력 받기 n, m = map(int, input().split()) # 2차원 리스트의 맵 정보 입력 받기 graph = [] for i in range(n): graph.append(list(map(int,input()))) # 모든 노드(위치)에 대하여 음료수 채우기 result = 0 for i in range(n): for j in range(m): # 현재 위치에서 DFS 수행 if dfs(i, j) == True: result += 1 print(result) -
DFS는 한번 수행되면 해당 노드와 연결된 모든 노드들도 방문처리해주고, 시작점 노드(해당 노드)가 방문처리되었다면, 즉 처음 방문하는 것이라면 그때만 result 값을 증가시킴
-
<문제> 미로 탈출
-
문제 해결 아이디어
-
BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색
-
상하좌우로 연결된 모든 노드로의 거리가 1로 동일하므로 (1, 1)지점부터 BFS를 수행하여 모든 노드의 최단 거리 값을 기록하여 해결
- 마지막 위치에 기록되어 있는 최단거리값을 출력 → 정답
-
-
답안 예시
# BFS 소스코드 구현 def bfs(x,y): # 큐 구현을 위해 deque 라이브러리 사용 queue = deque() queue.append((x,y)) # 큐가 빌 때까지 반복하기 while queue: x, y = queue.popleft() # 현재 위치에서 4가지 방향으로의 위치 확인 for i in range(4): nx = x + dx[i] ny = y + dy[i] # 미로 찾기 공간을 벗어난 경우 무시 if nx < 0 or nx >= n or ny < 0 or ny >= m: continue # 벽(괴물)인 경우 무시 if[nx][ny] == 0: continue if graph[nx][ny] == 1: graph[nx][ny] = graph[x][y] + 1 queue.append((nx,ny)) # 가장 오른쪽 아래까지의 최단 거리 반환 return graph[n-1][m-1] from collctions import deque # N, M을 공백을 기준으로 구분하여 입력 받기 n, m = map(int, input().split() # 2차원 리스트의 맵 정보 입력 받기 graph = [] for i in ragne(n): graph.append(list(map(int,input()))) # 이동할 네가지 방향 정의 dx = [-1,1,0,0] dy = [0,0,-1,1] #BFS 수행 결과 출력 print(bfs(0,0))
참고: 이것이 취업을 위한 코딩 테스트다 with 파이썬 (취업과 이직을 결정하는 알고리즘 인터뷰 완벽 가이드), 유튜브 강의 영상
