[코딩테스트] 쉽게 이해하고 바로 쓰는 DFS (깊이 우선 탐색)

DFS (깊이 우선 탐색)

DFS 깊이 우선 탐색은 코딩테스트에서 기본적으로 알아야한다. DFS란 말 그대로 깊이를 우선적으로 탐색하는 방법이다. 좀 더 쉽게 말하면, 갈림길이 있다면 한방향으로 끝까지 간 후에 답을 확인하는 과정을 반복한다. 따라서 재귀함수를 기본적으로 이해를 해야한다. 재귀함수관련 내용은 아래의 링크를 확인하자. 사실 그런말이 있다. DFS는 스택(stack)를 이용하고 BFS는 큐(Queue)를 이용한다. 그리고 DFS에서 스택을 쓸 수 있다고 할 수 있지만, 이는 원론적인 개념에 대한 이야기이고, 코딩테스트에서는 보통 재귀를 쓴다. 우선 비선형 구조에 대해 간단히 알아보고 DFS를 마스터 해보자.

 

https://han-py.tistory.com/224

[python] 재귀함수(recursive function)

 

코딩테스트에서 DFS와의 양대산맥은 BFS이다. BFS관련은 아래의 링크를 확인하자.

han-py.tistory.com/36

[python] BFS 문제 풀기

 

 

 

 

1. 선형구조와 비선형구조

실전 문제풀이 스킬을 넘어가기 전에 DFS 응용 문제를 풀기위한 기초개념인, 알고리즘 구조에 대한 이야기를 해보겠다. 

1.1 선형구조

선형구조란 여러개의 데이터들이 있을 때, 하나의 데이터 뒤에 하나의 데이터가 존재하는 것이다. 리스트 같이 index값을 순차적으로 구성되어 있는 것이 선형구조이다. 쉽게 말해서 배열에 for문으로 완전검색하여 풀수 있는 문제를 선형구조라고 할 수 있다. 이와 반대로 단순한  for문을 통해 데이터를 탐색할 수 없는 구조가 비선형구조라고 할수 있다.

 

1.2 비선형구조

 비선형 구조는 그래프(Graph)와 트리(Tree)로 나뉜다.

• 아래의 그림을 참고하면, 그래프는 n:n관계이다. (cycle이 있다. 즉, 계측구조를 나눌 수 없는 경우도 존재한다.)
• 트리는 1:n 관계이다.(cycle없다. 부모 하나에 여러 자식이 나옴. 계층구조와 방향성이 없음).

그래프와 트리의 포함관계는 '그래프 > 트리 > 이진트리(binary tree)'로 그래프가 트리를 포함하고 있다고 할 수 있다.

그래프에서 cycle이 없으면 트리가 된다.

 

cf. 이진트리란 모든 노드가 정확하게 두 개의 서브트리를 가지고 있는 트리이다.  다만 서브트리는 공백이 될 수 있다.

우리는 비선형구조를 풀 때 DFS와 BFS를 사용한다. DFS는 시작 점정의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법이라고 할 수 있다.

 

 

 

 

 

2. DFS

 사실 스택으로 DFS를 푼다고는 하지만, 여기서는 재귀로 푼다. 스택은 간단히 보고 스택 블로그에서 따로 자세히 다루도록 하겠다. 그리고 사실 재귀도 함수 호출하면 시스템 스택에 쌓이게 되므로 스택이라고 말하자면 말 할 수 있다. 아래는 스택의 흐름도를 먼저 보고, DFS 알고리즘의 스택을 활용한 슈도코드를 보자.

당장 문제 푸는게 바쁘다면 스택을 안보고 넘어가도된다.

 

 

2.1 스택(후입선출)구조의 흐름도

1. 시작 정점의 한 방향으로 갈 수 있는 곳까지 깊이 탐색한다. (가면서 지나가는 것들을 하나씩 담는다)
2. 가다가 더 이상 갈 곳이 없으면 가지막에 만났던 갈림길 간선이 있는 정점으로 되돌아온다.
3. 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문한다.
4. 가장 마지막에 만났던 갈림길의 점점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택을 사용한다.

결론은 DFS는 한번에 갈 수 있는 곳까지 쭉 간다. 가는 길에 다음 길로 가기전에 스택에 하나씩 넣고 간다. 더 이상 갈 길이 없으면 복귀해서 다시 다음 길로 간다. 즉, 복귀를 한다는 의미에서 스택을 사용한다고 할 수 있다..

 

2.2 스택을 활용한 슈도코드

1. 시작 점점 v를 결정하여 방문한다.(visited 체크)
2. 정점 v에 인접한 정점 중에서 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push하고 정점 w를 방문한다. 그리고 w를 v로 하여 다시 2를 반복한다.(주의-v에서 방문 한 곳이 있을 떄만 push를 한는 것이고 v에서 방문 할 곳이 없다면 push없이 되돌아간다.) 방문하지 않은 정점이 없다면, 탐색 방향을 바꾸기 위해 pop하여 마지막 방문 점점을 v로 하여 2를 반복한다.
3. 스택이 공백이 될 떄 까지 2를 반복한다.

즉, 되돌아 오기 위해 사용한 자료구조로 스택을 사용했다는 것을 기억해야한다.

 

 

 

 

3. 유형별 코드

여기서 부터는 스택으로 안풀고 dfs로 푼다. 실전 풀이.

3.1 간선

시작정점은 1이고 깊이우선탐색 경로를 출력해 보자. 첫번째 입력은 노드와 노드를 이어수는 간선의 수이다. 두번째 입력은 연결되어 있는 노드를 전부 표현한 것이다.

입력

7  8

1 2 1 3 2 4 2 5 4 6 5 6 6 7 3 7

 

 

그림으로 나타내 보면 다음과 았다.

DFS의 핵심은 방문하자마자 visited를 체크하는 것이다. 인접행렬로 푼다.

def dfs(v):
    visited[v] = 1
    print(v, end=" ")
    
    for w in range(V+1):
        if G[v][w] == 1 and visited[w] == 0: # 간선으로 연결되어 있고, 방문을 안했다면 dfs!
            dfs(w)



V, E = map(int, input().split())
temp = list(map(int, input().split()))

#간선을 넣는 곳이다(2차원으로 바꿔주자.)
G = [[0 for _ in range(V+1)] for _ in range(V+1)]

# 방문을 체크해 주는 곳이다.
visited = [0 for _ in range(V+1)]

for i in range(0, len(temp), 1): # 1 2 가 들어오면 1, 2와 2, 1을 둘다 체크한다
    G[temp[i]][temp[i+1]] = 1
    G[temp[i+1]][temp[i]] = 1
    
# 1에서 시작하기 때문에 1을 대입하자
dfs(1)

 

 

 

 

 

3.2 단지번호 붙이기

정사각형 모양의 지도에서 1은 집이 있고, 0은 집이 없는 곳을 나타낸다. 상하좌우로만 1이 연결되어 있으면 하나의 단지라고 할 수 있다. 그렇다면 주어진 입력에는 몇개의 단지가 있을까?

ex) 입력값

7              # 정사각형의 크기

0110100     # 지도

0110101

1110101

0000111

0100000

0111110

0111000

 

출력

3               # 1로 연결되는곳은 3군데이므로 3을 출력한다.

 

 

 

코드 구현 시 초보자들이 실수하는 가장 큰것이 visited 배열을 안만드는 것이다. 반드시 만들어 주자. 그리고 여기서 핵심은 상하좌우로 갈 수 있는 델타 함수가 포함되어 있다는 것이다.

 

def dfs(x, y, group):
    visited[x][y] = 1
    data[x][y] = group
    count[group] += 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if not (0 <= nx < N and 0 <= ny <= N):
            continue
        if visited[nx][ny]:
            continue
        if data[nx][ny] == 0:
            continue
        dfs(nx, ny, group)
    

N = int(nput())
data = [list(map(int, input()) for _ in range(N)]
visited = [[0 for _ in range(N)] for _ in range(N)]
group = 1

# 델타 탐색
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
count = [0] * (N*N+1)

for i in range(N):
    for j in range(N):
        if data[i][j] and visited[i][j] == 0:
            dfs(i, j, group)
            group += 1
            
count.sort()
print(group-1)

 

같은 문제 다른 풀이! 델타 탐색을 배열로 넣어도된다. 아래 풀이의 특징은 visited를 따로 만들지 않고 기본 data를 바꿔서 풀었다. 이 부분도 기억해 놓자.

def(x, y):
    data[x][y] = 0
    ret = 0
    for (dx, dy) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        xx, yy = x+dx, y+dy
        if not (0 <= xx < N and 0 <= yy < N):
            continue
        if data[xx][yy]:
            ret += dfs(xx, yy)
    return ret+1

N = int(input())
data = [list(map(int, input)) for _ in range(N)]
res = []
for i in range(N):
    for j in range(N):
        if data[i][j]:
            res.append(dfs(i, j))
res.sort()
print(len(res))
for i in res:
    print(i)