DFS

DFS(Depth First Search)는 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

 

DFS는 스택 자료구조를 이용하며 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 스택에 삽입하고 방문처리를한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

DFS는 스택을 사용하는 알고리즘이기 때문에 재귀 함수를 이용했을 때 간결하게 구현할 수 있다.

def dfs(graph, current_node, visited):
    # 현재 노드를 방문 처리
    visited[current_node] = True
    print(current_node, end=' ')

    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for connected_node in graph[current_node]:

        # 연결된 노드를 방문하지 않았다면 -> 종료 조건이 되기도 함
        if not visited[connected_node]:
            # dfs 함수 호출
            dfs(graph, connected_node, visited)

# 각 노드가 연결된 정보를 2차원 리스트로 표현
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

visited = [False] * 9

dfs(graph, 1, visited)

1 2 7 6 8 3 4 5

 

 

이제 DFS 예시 문제를 보자.

 

문제

• N x M 크기의 얼음 틀이 있다. 구멍이 뚫려있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라.

 

입력 조건

• 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다 (1 <= N, M <= 1000)
• 두 번쨰 줄부터 N + 1번째 줄까지 얼음 틀의 형태가 주어진다.

ex)

00110
00011
11111
00000

 

 

키 아이디어는 다음과 같다.

• 얼음 틀의 형태를 행렬로 생각하고 이중 반복문으로 모든 좌표에 대해 dfs를 수행한다. 
• 이중 반복문에 의해 특정 좌표(3x3이면 9개의 좌표들)에 대해 처음 dfs가 수행되었을 때, 그 좌표가 방문하지 않은 노드면 True를 리턴, 아니면 False를 리턴한다.
• 다른 말로 설명하면, 재귀 함수는 스택 자료구조를 이용한다. 스택에 더 이상 실행할 함수가 존재하지 않을 때 True를 리턴하게 된다.

# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())

# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

# DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문
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

# 모든 노드(위치)에 대하여 음료수 채우기
result = 0
for i in range(n):
    for j in range(m):
        # 현재 위치에서 DFS 수행
        if dfs(i, j) == True:
            print(i, j)
            result += 1

print(result) # 정답 출력

 

 

이중 반복문의 if 문 안에 print(i, j)를 넣어 어떤 좌표에서 True가 리턴되는지를 확인해 보면 다음과 같다.

0 0
1 2
2 1
3

 

예를 들어 (0, 1)도 처음에는 비어있었지만 (0, 0)에서 실행한 dfs로 인해 방문처리가 되어 True가 리턴되지 않는다.