그래프 탐색 알고리즘 : DFS/BFS
- 탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
- DFS와 BFS는 대표적인 그래프 탐색 알고리즘
- DFS/BFS는 코딩 테스트에서 매우 자주 등장하는 유형으로 반드시 숙지해야 함
DFS (Depth-First Search)
- DFS : 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
- DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며, 다음과 같이 동작한다.
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 더 이상 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차원 리스트로 각 노드가 연결된 정보를 표현
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)C++로 DFS 구현
#include <iostream>
#include <vector>
using namespace std;
bool visited[9];
vector<int> graph[9];
// DFS 함수 정의
void dfs(int x)
{
// 현재 노드를 방문 처리
visited[x] = true;
cout << x << ' ';
// 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for (int i = 0; i < graph[x].size(); i++)
{
int y = graph[x][i];
if (!visited[y])
dfs(y);
}
}
int main(void)
{
// 노드 1에 연결된 노드 정보 저장
graph[1].push_back(2);
graph[1].push_back(3);
graph[1].push_back(8);
// 노드 2에 연결된 노드 정보 저장
graph[2].push_back(1);
graph[2].push_back(7);
// 노드 3에 연결된 노드 정보 저장
graph[3].push_back(1);
graph[3].push_back(4);
graph[3].push_back(5);
// 노드 4에 연결된 노드 정보 저장
graph[4].push_back(3);
graph[4].push_back(5);
// 노드 5에 연결된 노드 정보 저장
graph[5].push_back(3);
graph[5].push_back(4);
// 노드 6에 연결된 노드 정보 저장
graph[6].push_back(7);
// 노드 7에 연결된 노드 정보 저장
graph[7].push_back(2);
graph[7].push_back(6);
graph[7].push_back(8);
// 노드 8에 연결된 노드 정보 저장
graph[8].push_back(1);
graph[8].push_back(7);
dfs(1);
}BFS (Breadth-First Search)
- BFS : 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
- BFS는 큐 자료구조를 이용하며 다음과 같이 동작한다.
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
파이썬으로 BFS 구현
from collections import deque
def bfs(graph, start, visited):
# 방문할 노드를 저장할 큐
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)C++로 BFS 구현
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
bool visited[9];
vector<int> graph[9];
void bfs(int start)
{
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty())
{
int x = q.front();
q.pop();
cout << x << ' ';
for (int i = 0; i < graph[x].size(); i++)
{
int y = graph[x][i];
if (!visited[y])
{
q.push(y);
visited[y] = true;
}
}
}
}
int main(void)
{
// 노드 1에 연결된 노드 정보 저장
graph[1].push_back(2);
graph[1].push_back(3);
graph[1].push_back(8);
// 노드 2에 연결된 노드 정보 저장
graph[2].push_back(1);
graph[2].push_back(7);
// 노드 3에 연결된 노드 정보 저장
graph[3].push_back(1);
graph[3].push_back(4);
graph[3].push_back(5);
// 노드 4에 연결된 노드 정보 저장
graph[4].push_back(3);
graph[4].push_back(5);
// 노드 5에 연결된 노드 정보 저장
graph[5].push_back(3);
graph[5].push_back(4);
// 노드 6에 연결된 노드 정보 저장
graph[6].push_back(7);
// 노드 7에 연결된 노드 정보 저장
graph[7].push_back(2);
graph[7].push_back(6);
graph[7].push_back(8);
// 노드 8에 연결된 노드 정보 저장
graph[8].push_back(1);
graph[8].push_back(7);
bfs(1);
}BFS/DFS 문제 풀이
문제1 : 음료수 얼려 먹기
솔루션 코드
# 음료수 얼려 먹기 문제
# dfs를 이용해 주변의 0인 노드를 탐색하고 방문하는 함수
def dfs(x, y):
# 주어진 범위를 벗어나는 경우에는 즉시 종료
if x <= -1 or x >= n or y <= -1 or y >= m:
return False
# 현재 노드가 0 이라면
if graph[x][y] == 0:
# 해당 노드를 1로 바꾸고 상하좌우 연결된 0인 노드도 모두 1로 바꾸기
graph[x][y] = 1
# 상 하 좌 우 모두 확인
dfs(x, y - 1)
dfs(x, y + 1)
dfs(x - 1, y)
dfs(x + 1, y)
return True
# 현재 노드가 1 이라면 False
return False
# n, m 입력
n, m = map(int, input().split())
# 얼음틀의 형태를 2차원 리스트로 저장
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# 모든 노드를 탐색하면서
# 해당 노드가 0 이라면 -> 연결된 0 노드를 모두 1로 바꾸고 result += 1
# 해당 노드가 1 이라면 -> pass
result = 0
for i in range(n):
for j in range(m):
# 현재 위치에서 DFS 수행
if dfs(i, j) == True:
result += 1
print(result)솔루션 코드 해설
- N x M 개의 입력 각각을 하나의 노드로 가지는 그래프를 가정하여 문제를 푼다.
- 저장된 값이 0인 노드는 방문하지 않은 노드, 저장된 값이 1인 노드는 방문한 노드라고 가정한다.
- 방문하지 않은 노드를 탐색할 때 DFS를 이용하여 탐색한다.
- 2중 for문을 이용하여 그래프의 모든 노드를 탐색하는데
- graph[i][j]가 0 이라면 → 아직 방문하지 않은 노드이므로 result 값을 +1 하고, dfs를 이용해 주변 모든 노드를 방문처리 한다.
- graph[i][j]가 1 이라면 → 이미 방문한 노드이기 때문에 넘어간다
- 위의 과정을 거치면 result값에 아이스크림 개수가 저장된다.
문제2 : 미로 탈출
해결 아이디어
- BFS를 이용한다!
- BFS는 간선의 비용이 모두 같을 때 최단 거리를 구할 수 있는 알고리즘이다. 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문
솔루션 코드
# 미로 탈출
from collections import deque
# n, m 입력
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# 상하좌우 방향벡터
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
queue = deque()
queue.append((0, 0))
while queue:
x, y = queue.popleft()
# 현재 위치에서 상하좌우로 위치 확인
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 graph[nx][ny] == 0:
continue
# 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx, ny))
# 가장 오른쪽 아래의 최단 거리 출력
print(graph[n-1][m-1])백준 문제풀이
1260번 : DFS와 BFS
솔루션 코드
# DFS와 BFS
from collections import deque
# 1. n, m, v 입력
n, m, v = map(int, input().split())
# 2. 간선 입력 & 그래프 생성
# 2차원 리스트 초기화
graph = [[] for _ in range(n + 1)] # n + 1개의 행을 가지는 2차원 리스트
# m개의 간선 정보 입력
for _ in range(m):
node1, node2 = map(int, input().split())
graph[node1].append(node2)
graph[node2].append(node1)
# 입력된 정보 정렬
for row in graph:
row.sort()
# 3. BFS 수행 결과 출력
def dfs(graph, v, visited):
# 현재 노드를 방문 처리
visited[v] = True
print(v, end=' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * (n+1)
# 정의된 DFS 함수 호출
dfs(graph, v, visited)
print()
# 4. BFS 수행 결과 출력
def bfs(graph, start, visited):
# 방문할 노드를 저장할 큐
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
# 각 노드의 방문 여부를 1차원 리스트로 표현
visited = [False] * (n+1)
# 정의된 BFS 함수 호출
bfs(graph, v, visited)
print()솔루션 해설
-
n, m, v 입력
n, m, v = map(int, input().split()) -
간선 입력 & 그래프 생성
# 2차원 리스트 초기화 graph = [[] for _ in range(n + 1)] # n + 1개의 행을 가지는 2차원 리스트 # m개의 간선 정보 입력 for _ in range(m): node1, node2 = map(int, input().split()) graph[node1].append(node2) graph[node2].append(node1) # 입력된 정보 정렬 for row in graph: row.sort()-
2차원 리스트 초기화
→ (노드의 개수 + 1)개 만큼의 행을 가지는 2차원 리스트를 초기화한다. -
m개의 간선 정보 입력
-
입력된 정보 정렬
→ 번호가 작은 노드부터 방문해야 하므로 오름차순으로 정렬한다.
-
-
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) # 각 노드가 방문된 정보를 표현 (1차원 리스트) visited = [False] * (n+1) # 정의된 DFS 함수 호출 dfs(graph, v, visited) print()- dfs 함수는 강의의 함수를 그대로 사용
- visited 리스트는 (노드의 수 + 1) 크기로 변경
- 입력받은 v 노드 부터 탐색 시작
-
BFS 수행 결과 출력
def bfs(graph, start, visited): # 방문할 노드를 저장할 큐 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 # 각 노드의 방문 여부를 1차원 리스트로 표현 visited = [False] * (n+1) # 정의된 BFS 함수 호출 bfs(graph, v, visited) print()- bfs 함수는 강의의 함수를 그대로 사용
- visited 리스트는 (노드의 수 + 1) 크기로 변경
- 입력받은 v 노드 부터 탐색 시작
2667번 : 단지번호붙이기
솔루션 코드
# 단지 번호 붙이기
def dfs(x, y):
# 주어진 범위를 벗어나는 경우에는 즉시 종료
if x <= -1 or x >= n or y <= -1 or y >= n:
return False
# 현재 노드가 0 이라면
if graph[x][y] == 1:
# 해당 노드를 1로 바꾸고 상하좌우 연결된 0인 노드도 모두 1로 바꾸기
graph[x][y] = 0
house_count[complex_index] += 1
# 상 하 좌 우 모두 확인
dfs(x, y - 1)
dfs(x, y + 1)
dfs(x - 1, y)
dfs(x + 1, y)
return True
# 현재 노드가 1 이라면 False
return False
# n
n = int(input())
# 얼음틀의 형태를 2차원 리스트로 저장
graph = []
for i in range(n):
graph.append(list(map(int, input())))
complex_count = 0 # 단지 수 카운트
house_count = [0] * 25 * 25 # 각 단지의 집 수(최대 25^2개까지 가능)
complex_index = 0 # 각 단지의 번호 -> 각 단지의 집 수를 카운트 하는 용도
for i in range(n):
for j in range(n):
# 현재 위치에서 DFS 수행
if dfs(i, j) == True:
complex_count += 1
complex_index += 1 # 그 다음 단지를 이용하기 위해
print(complex_count)
house_count = house_count[:complex_index]
house_count.sort()
for i in range(complex_index):
print(house_count[i])솔루션 해설
음료수 얼려먹기에서 수정한 내용
- n, m을 입력받는게 아니라 n만 입력받음
- 0이 방문하지 않은 노드로 처리되는게 아니라 1이 방문하지 않은 노드로 처리됨
- result가 단지의 수를 출력하는 것과 똑같음 (이름만 complex_count로 수정)
- 각 단지의 아파트 개수를 저장하기 위한 house_count 리스트 초기화 → 1을 탐색할 때마다 house_count 리스트의 각 단지번째 수가 +1 되도록 코드 작성
- 모든 탐색을 마치고
- complex_count 출력
- house_count 리스트를 정리하고, 정렬하여 출력
반성은 하되 후회하지 않는다😎