깊이 우선 탐색(Depth-First Search)

깊이 우선 탐색(DFS)란?

19세기에 프랑스 수학자 샤를 피에르 트레모가 미로를 풀기 위한 전략으로 연구하여,

트리 또는 그래프 데이터 구조를 탐색하거나 검색하기 위한 알고리즘이다.

---

알고리즘은 (시작)루트 노드(만약 그래프의 경우 임의 노드)에서 시작하여

역추적하기 전에 각 분기를 따라 가능한 멀리 탐색한다.

아래 그림을 통해 어떻게 DFS가 노드에 순차적으로 접근하는지 알 수있다.

처음 시작 노드에서 인접 노드로 움직이는데 한번 팠다면 끝까지 파는 깊이있는 알고리즘이다.(그래서 깊이 우선 탐색)

그렇다고 불도저 마냥 불가능해도 계속 한 우물만을 파는 녀석은 아니다. 

만약 가다가 더 이상 불가능한 노드(4)를 만났을 때는 그제서야  돌아가 다른 최근 노드(5)로 우물을 판다.

 

해당 각 노드는 인접리스트와 인접 행렬로 이뤄질 수 있으며, 방향 무방향으로도 나눠질 수 있는데

해당 설명은 자료구조 (트리와 그래프)를 참고하자. 

 

---

그럼 이렇게 서로 인접한 노드를 깊이있게 탐색하는 방법이 어디에 쓰일까? 

백준 문제로 감을 잡아보자. 

 

1012번: 유기농 배추

해당 문제는 0(땅) 1(배추)로 이루어진 행렬에서 배추가 인접하면 하나의 집합으로 인식하고

몇개의 집합이 나오는지 알아내는 문제다.

 

01000110

01000010

00001000

 

위와 같은 밭에서 눈으로 샌다면 배추의 묶음은 3개다

반복문을 통해 하나씩 접근하다가 1(배추)를 만나면 총개수를 1+해주고

해당 배추와 인접한 1을 찾아 0으로 바꾸어 나가면 된다. 

그렇게되면 인접했던 배추들의 묶음 하나는 총 개수 +1 이되어 하나의 묶음 개수가 증가한다. 

 

t = int(input())
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x, y):
    queue = [[x, y]]
    while queue:
        a, b = queue[0][0], queue[0][1]
        del queue[0]
        for i in range(4):
            q = a + dx[i]
            w = b + dy[i]
            if 0 <= q < n and 0 <= w < m and s[q][w] == 1:
                s[q][w] = 0
                queue.append([q, w])
for i in range(t):
    m, n, k = map(int, input().split())
    s = [[0] * m for i in range(n)]
    cnt = 0
    for j in range(k):
        a, b = map(int, input().split())
        s[b][a] = 1
    for q in range(n):
        for w in range(m):
            if s[q][w] == 1:
                bfs(q, w)
                s[q][w] = 0
                cnt += 1
    print(cnt)

---

맨 처음 소개했던 것과 같이 DFS알고리즘은 미로탐색을 위해 만들어진 알고리즘이다.

오직 0 1 로 이루어진 행렬뿐만 아니라 False True , 노드 번호, 경우의 수등 

그래프 ,트리로 모든 경우를 구현하여 우리가 원하는 결과를 DFS를 통해 찾을 수 있다. 

 

 

 

 

그림참고 ) https://ko.m.wikipedia.org/wiki/%ED%8C%8C%EC%9D%BC:Depth-First-Search.gif