DFS 와 BFS
1. 깊이 우선 탐색 (DFS, Depth-First Search)
최대한 깊게 탐색한 후 더 이상 내려갈 곳이 없는 경우 옆으로 이동하여 탐색
DFS의 개념
시작 노드에서 탐색을 시작하여 다음 분기(branch)로 넘어가기 전에 해당 분기를 끝까지 탐색하고 다음 분기로 넘어가는 방식
순서와 상관없이 처리해도 되지만 코딩테스트 등에서는 관행적으로 번호가 낮은 순서부터 처리하도록 구현
DFS의 특징
- 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색
- 스택 혹은 재귀함수로 구현
2. 너비 우선 탐색(BFS)
최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동
BFS는 시작 노드에서 인접한 노드를 먼저 탐색하는 방법으로, 가까운 정점을 먼저 방문하고 그 후에 멀리 있는 정점을 나중에 탐색하는 것이 특징이다.
인접한 노드를 먼저 방문하기 때문에 두 노드 사이의 최단경로 등을 구하는 문제를 해결하기 좋음.
BFS의 특징
- 현재 정점에 연결된 가까운 점들부터 탐색
- 큐(queue)를 이용해서 구현
구현
- 두 방법 모두 방문했던 노드를 다시 방문하지 않아야 하므로 방문 정보를 리스트 등으로 표현 해야 한다.
다음과 같은 그래프를 노드 1을 시작 노드로 설정하고 탐색할 것이다.
DFS의 구현
- 방문처리
- 인접한 노드의 방문여부 확인 후 방문하지 않은 노트면 재귀함수 호출
# 재귀함수로 구현
def dfs(graph, v, visited):
visited[v] = True
print(v, end=' ')
for i in graph[b]:
if not visited[i]:
dfs(graph, i, visited)
# 이차원 리스트를 이용해 인접 행렬 표현
graph = [
[],
[2, 3, 8]
[1, 7]
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False] * 9
dfs(graph, 1, visited)
출력결과: 1 2 7 6 8 3 4 5
BFS의 구현
- 방문처리
- 인접 노드가 방문하지 않은 노드면 queue에
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
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False] * 9
bfs(graph, 1, visited)
시간복잡도
DFS -> O(N) BFS -> O(N) (실제 수행시간은 대체적으로 DFS보다 빠름)
문제
음료수 얼려 먹기
문제
N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.
구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.
이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라.
다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개가 생성된다
입력
- 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 <= N, M <= 1,000)
- 두 번째 줄부터 N + 1 번째 줄까지 얼음 틀의 형태가 주어진다.
- 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.
출력
한 번에 만들 수 있는 아이스크림의 개수를 출력한다.
입력 예시 1
4 5
00110
00011
11111
00000
출력 예시 1
3
입력 예시 2
15 14
00000111100000
11111101111110
11011101101110
11011101100000
11011111111111
11011111111100
11000000011111
01111111111111
00000000011111
01111111111000
00011111111000
00000001111000
11111111110011
11100011111111
11100011111111
출력 예시2
8
풀이
나의 풀이
-
이 문제는 BFS, DFS중 어떤 방법을 택해도 되지만 평소 자주 쓰지 않았던 DFS를 재귀호출을 이용하여 품
-
또한 이 문제는 visited 사용하지 않고 풀 수 있고 visited를 쓰지 않는 것이 더 메모리를 덜 사용하지만 DFS풀이의 일관성을 위해 사용
import sys
N, M = map(int, sys.stdin.readline().split())
graph = [[]for _ in range(N+1)]
for i in range(N):
nums = list(sys.stdin.readline().strip())
graph[i] = list(map(int, nums))
visited = [[False for _ in range(M)] for i in range(N)]
moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def dfs(x, y):
if x < 0 or x >= N or y <0 or y >= M:
return False
if visited[x][y] or graph[x][y]:
return False
visited[x][y] = True
for move in moves:
dfs(x + move[0], y + move[1])
return True
ans = 0
for j in range(N):
for k in range(M):
if not graph[j][k] and not visited[j][k]:
if dfs(j, k):
ans += 1
print(ans)