DFS/BFS 활용 유형
- 경로 탐색 유형(최단 거리, 시간)
- 네트워크 유형(연결성 판별)
- 조합 유형(모든 조합 만들기)
DFS(Depth First Search)
너비와 깊이 중 깊이를 우선하여 그래프를 탐색하는 방법이다.
활용 문제
- 미로 찾기
- 그래프의 전체 연결 여부 확인 - 주어진 그래프가 하나로 연결되어 있는가?
- 깊이 우선 탐색 우선 순위 문제
장단점
- 장점 : 간단한 구현(재귀 함수 코드 짧음), 메모리 효율(BFS 비해), 경로 관련 문제(최단 경로가 아닌 모든 경로)
- 단점 : 시간이 오래 걸린다 → BFS 활용하기
구현 방법
DFS는 Stack과 재귀함수 두 가지의 방법을 통해 구현할 수 있다.
Stack을 활용한 구현
Stack을 활용한 구현 설명
- 탐색 시작 노드를 스택에 삽입, 방문 처리
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
# 각 노드가 연결된 정보를 표현 (2차원 리스트)
# 인접리스트 방식으로 그래프 표현
graph = [
[], # 보통 노드는 1번부터 시작하므로 인덱스 0은 비움
[2, 3, 8], # 1번 노드와 연결된 2, 3, 8번 노드
[1, 7], # 2번 노드와 연결된 1, 7번 노드
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 표현 (1차원 리스트)
# default는 False
visited = [False] * 9 # 인덱스 0은 사용 X, 노드 8개+1의 크기의 리스트
# 스택을 이용한 DFS 메서드 정의
def dfs(graph, start):
stack = [] # 스택 생성
visited[start] = True # 시작 노드를 방문 처리
stack.append(start) # 시작 노드를 스택에 삽입
while stack: # 스택이 비어있지 않은 동안 반복
current_node = stack[-1] # 스택의 맨 위 노드를 가져옴
unvisited_neighbor = False # 방문하지 않은 이웃 노드가 있는지 확인하기 위한 플래그
# 현재 노드와 연결된 이웃 노드 중에서 방문하지 않은 노드를 스택에 추가
for neighbor in graph[current_node]:
if not visited[neighbor]:
stack.append(neighbor) # 방문하지 않은 이웃 노드를 스택에 추가
visited[neighbor] = True # 이웃 노드를 방문 처리
unvisited_neighbor = True # 방문하지 않은 이웃 노드가 있다고 표시
break # 이웃 노드를 하나 추가하고 반복문 종료
if not unvisited_neighbor:
# 현재 노드의 모든 이웃 노드를 방문했거나 이웃 노드가 없는 경우
stack.pop() # 현재 노드를 스택에서 제거
print(current_node, end=' ') # 현재 노드 출력
# 정의된 DFS 함수 호출
dfs(graph, 1) # 출력: 1 2 7 6 8 3 4 5
- Stack은 LIFO(후입선출) 자료구조이기 때문에, 가장 최근에 넣은 것들을 꺼내기 적합하여 DFS 구현에 좋다.
재귀함수를 활용한 구현
재귀함수를 사용하면 현재 경로를 스택에 저장하고, 스택을 통해 이전 경로로 돌아갈 수 있어서 DFS를 자연스럽게 구현할 수 있다.
- 탐색 시작 노드를 방문 처리
- 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드로 이동, 재귀함수를 호출하여 현재 경로에 노드를 추가, 그 노드에서 다시 DFS. 방문하지 않은 인접 노드가 없으면 현재 노드에서 이전 단계로 돌아가서 다시 탐색.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
# 각 노드가 연결된 정보를 표현 (2차원 리스트)
# 인접리스트 방식으로 그래프 표현
graph = [
[], # 보통 노드는 1번부터 시작하므로 인덱스 0은 비움
[2, 3, 8], # 1번 노드와 연결된 2, 3, 8번 노드
[1, 7], # 2번 노드와 연결된 1, 7번 노드
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 표현 (1차원 리스트)
# default는 False
visited = [False] * 9 # 인덱스 0은 사용 X, 노드8개+1의 크기의 리스트
# 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)
# 정의된 DFS 함수 호출
dfs(graph, 1, visited) # 출력: 1 2 7 6 8 3 4 5
음료수 얼려 먹기 문제 - 덩어리 찾기(섬 구분)(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
코드
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 = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input()))
result = 0
for i in range(n):
for j in range(m):
if dfs(i, j) == True:
result += 1
print(result)