1. 깊이 우선 탐색(DFS) 소개
깊이 우선 탐색(Depth-First Search, DFS)은 그래프의 탐색 알고리즘 중 하나로,
주어진 노드에서 가능한 깊이까지 탐색한 후, 더 이상 탐색할 노드가 없으면 마지막으로
방문했던 노드로 되돌아가서 다른 경로를 탐색하는 방식입니다. 이 방법은 그래프의 형태에 따라
다양한 용도로 사용되며, 트리의 탐색과 연결 요소의 탐색, 경로 탐색 문제 등에 활용됩니다.
DFS의 작동 방식은 다음과 같습니다:
- 시작 노드를 스택에 추가한다.
- 스택에서 노드를 하나 꺼내 탐색한다.
- 탐색한 노드를 방문한 것으로 표시한다.
- 아직 방문하지 않은 인접 노드를 모두 스택에 추가한다.
- 스택이 비어있지 않은 동안 위 과정을 반복한다.
2. 문제 설명
문제: 섬의 개수 세기
주어진 2차원 배열 grid에서 ‘1’은 육지를, ‘0’은 바다를 나타냅니다.
한 섬은 상하좌우로 연결된 육지의 집합입니다.
섬의 개수를 세는 함수를 작성하세요.
입력:
grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
출력: 3
3. 문제 해결 과정
3.1. 문제 이해하기
문제를 해결하기 위해서는 먼저 육지가 연결된 부분(즉, 섬)을 찾아야 합니다.
각각의 섬은 DFS를 통해 찾을 수 있으며, 육지를 탐색하면서 인접한 육지도 함께 탐색하여
섬의 모든 부분을 확인할 수 있습니다.
3.2. 데이터 구조 설계하기
DFS를 구현하기 위해 스택을 사용하겠습니다.
자원을 효율적으로 관리하기 위해 2차원 배열의 모든 요소를 방문 여부를 체크할 수 있는
boolean 배열을 사용할 것입니다.
3.3. DFS 구현하기
def dfs(grid, visited, i, j):
# 범위를 벗어나거나 이미 방문한 경우 종료
if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or visited[i][j] or grid[i][j] == '0':
return
# 현재 위치 방문 처리
visited[i][j] = True
# 상하좌우 탐색
dfs(grid, visited, i - 1, j) # 위
dfs(grid, visited, i + 1, j) # 아래
dfs(grid, visited, i, j - 1) # 왼쪽
dfs(grid, visited, i, j + 1) # 오른쪽
3.4. 최종 함수 구현하기
def numIslands(grid):
if not grid:
return 0
visited = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]
island_count = 0
# 그리드의 모든 노드 탐색
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1' and not visited[i][j]:
dfs(grid, visited, i, j)
island_count += 1 # 새로운 섬 찾음
return island_count
3.5. 코드 테스트
grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
print(numIslands(grid)) # 3이 출력되어야 합니다.
4. 문제 해결 리뷰
DFS를 활용하여 문제를 해결하였고, 시간 복잡도는 O(N * M)이며,
N은 행의 수, M은 열의 수를 나타냅니다.
모든 노드를 최대 한 번씩 방문하기 때문에 효율적인 방법이라고 할 수 있습니다.
또한, 공간 복잡도 또한 O(N * M)이 들어간다고 할 수 있습니다.
이는 visiting 리스트를 위해 추가적인 공간을 사용했기 때문입니다.
DFS는 메모리 사용량이 높을 수 있지만, 문제의 성격이나 크기에 따라 BFS보다 효과적인 경우가 많습니다.
특히, 경로 문제나 연결 구성 요소를 구별하는 문제에서 DFS의 장점을 누릴 수 있습니다.
5. 결론
이번 강좌를 통해 DFS의 기본 개념과 문제 해결 방식에 대해 알아보았습니다.
다양한 문제에서 DFS를 활용할 수 있으니, 본 강좌를 바탕으로 여러 문제를 풀어보시기 바랍니다.
감사합니다.