모든 경우의 수를 탐색하여 답을 찾아야 하는 완전 탐색 문제는 단순하지만 코딩 테스트 문제로 상당히 자주 출제된다. 특히 복잡한 규칙이 주어지고 그 규칙에 따라 완전탐색을 구현하여 해결하는 문제가 자주 보이는데 어렵지는 않지만 문제를 이해하는 데도 오래걸리고 구현과 디버깅에도 시간을 상당히 많이 소모하게 되기 때문에 많이 풀어서 익숙해질 필요가 있는 영역이다. 이번에는 완전탐색 중에도 DFS(깊이 우선 탐색)와 DFS 관련 문제들을 알아본다.
1. DFS(Depth First Search)
DFS는 시작 노드에서부터 갈 수 있는 데 까지 계속해서 다음 노드로 이동하다가 더이상 이동할 수 있는 노드가 없다면 이동할 수 있는 노드를 찾을 떄 까지 이전 노드로 돌아가기를 반복하는 방식의 완전탐색 알고리즘이다. 그림으로 표현하자면 다음과 같다.
위와 같이 트리를 DFS로 방문할 경우 방문 순서는 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 이 된다.
본래 DFS는 스택으로 구현되는 탐색 알고리즘이지만 실제로 구현할 때는 대부분 직접 스택을 사용하여 구현하기보다는 재귀를 사용하여 구현하게 된다. 인접리스트 방식으로 그래프를 표현할 경우 모든 정점과 간선을 탐색하기에 O(|V|+|E|), 인접행렬 방식일 경우 O(|V|^2)의 시간복잡도를 보인다. DFS는 두 정점의 연결 여부를 확인하거나 서로 연결된 노드들을 하나의 부분집합으로 볼 때 부분집합의 갯수를 세는 등의 문제에 활용된다.
2. 두 정점의 연결여부 확인
한 노드에서 시작하여 DFS를 호출하면 그 노드와 직/간접적으로 연결된 모든 노드를 탐색하기 때문에 두 정점이 연결되어있는지 확인 가능하다. 관련 문제(https://www.acmicpc.net/problem/2606)를 DFS를 활용하여 해결한 코드는 다음과 같다.
import sys
input = sys.stdin.readline
def sol2606():
# 정점의 수
n = int(input())
# 간선의 수
m = int(input())
# 인접리스트 그래프
g = [[] for _ in range(n+1)]
for i in range(m):
s, e = map(int, input().split())
g[s].append(e)
g[e].append(s)
# DFS 함수
def dfs(node):
# 현재 노드의 모든 인접 노드중 아직 방문하지 않은 노드에 대해
# 방문처리 및 DFS함수 재귀호출
for adj in g[node]:
if not visit[adj]:
visit[adj] = True
dfs(adj)
# 1번 컴퓨터부터 탐색 시작
visit = [False]*(n+1)
visit[1] = True
dfs(1)
# 방문표시된 컴퓨터 수 - 1 (1번컴퓨터는 포함하지 않음)
return visit.count(True)-1DFS를 사용하여 1번 컴퓨터와 연결된 정점의 갯수를 모두 찾아내는 문제였다. 간단하지만 DFS에 대한 기본적인 이해를 다지고 넘어가기엔 적당하다.
3. 연결된 부분집합의 갯수 세기
연결그래프가 아닌 경우, 한 노드에서 시작하여 DFS를 실행하더라도 방문되지 않는 노드가 있을 수 있다.
이러한 경우 그 노드들에 대해서도 순차적으로 DFS를 호출하면 DFS의 호출 횟수(재귀호출 제외)로 연결된 부분집합의 갯수를 알아낼 수 있다. 관련 문제(https://www.acmicpc.net/problem/2667)를 DFS로 해결한 코드는 다음과 같다.
import sys
input = sys.stdin.readline
def sol2667():
n = int(input())
land = [list(input().rstrip()) for _ in range(n)]
# 깊이우선탐색 함수
def dfs(r, c):
# 방문한 땅에 표시
land[r][c] = 'x'
# 단지에 포함된 집의 갯수 카운트
cnt = 1
# 상/하/좌/우 칸 중 집이 있고 아직 방문하지 않은 경우
# 단지에 포함시키고 dfs 재귀호출
for nr, nc in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]:
if 0<=nr<n and 0<=nc<n and land[nr][nc]=='1':
cnt += dfs(nr, nc)
# 단지에 포함된 집의 수 반환
return cnt
# 지도를 순차적으로 순회하며 방문하지 않은 집마다 dfs 호출
res = [0]
for i in range(n):
for j in range(n):
if land[i][j] == '1':
res.append(dfs(i, j))
# 단지의 수와 단지에 포함된 집의 수를 오름차순정렬한 결과를 반환
res.sort()
res[0] = len(res) - 1
return '\n'.join(map(str, res))
if __name__ == '__main__':
print(sol2667())dfs를 이러한 형태로 활용하는 문제는 굉장히 자주 등장한다. 다만 이 문제처럼 간단한 것 보다는 좀더 복잡한 경우가 대부분이다. 재귀를 활용하는 만큼 작은 실수로 예상치 못한 버그가 발생할 수 있으며 python의 경우 재귀가 그다지 효율적이지 못해 정상적으로 코드를 짜더라도 AC를 받지 못하는 문제도 종종 있기 때문에 보조언어로 C++ 등의 속도가 빠른 언어를 하나쯤 익혀둘 필요가 있다.
'코딩테스트 > 알고리즘' 카테고리의 다른 글
| #20 트리 동적계획법 (0) | 2021.08.23 |
|---|---|
| #19 완전 탐색 - BFS(Breadth First Search) (0) | 2021.08.21 |
| #17 동적 계획법(Dynamic Programming) 1 - 기본 (0) | 2021.08.19 |
| #16 우선순위 큐(Priority Queue) (0) | 2021.08.18 |
| #15 이분 탐색(Binary Search) (0) | 2021.08.17 |
