Connected Components with DFS

벽으로 둘러싸인 공간, 즉 방의 갯수를 구하는 Counting Rooms 라는 문제가 있다.

https://cses.fi/problemset/task/1192/

CSES - Counting Rooms

이는 DFS의 응용 형태로 푸는 것이다. DFS는 한 점에서 출발해 닿을 수 있는 미 방문점을 모두 방문하는 것이다. 방문할 때 마다 방문된 점을 표시하되 끝까지 방문이 되면 돌아온다. 이와 유사한 과정인 backtracking은 방문시마다 어떤 조건에 대해 확인하는 절차를 거쳐, 그 조건이 만족되지 않으면 방문을 종료하는 것이다. DFS에서 기본적으로 검증하는 조건은 바로 '방문여부'가 된다. 이미 방문된 것은 다시 방문하지 않는다. 이를 위해 방문된 노드에 대한 기호를 모아놓는 일을 set이나 array를 통해 할 수 있다. set에 새로 방문하려는 노드가 포함되어 있는지 확인하는 것은 O(1), array의 경우도 각 index가 node의 id를 나타내므로 O(1)으로 확인할 수 있다. 공간복잡도의 차이만 있다.

첫번째 작성한 코드는 이런 기본적 원칙에 입각해서 작성했다.

import sys
sys.setrecursionlimit(10**6)
#sys.stdin = open('cr.txt', 'r')
 
'''
Example
 
Input:
5 8
########
#..#...#
####.#.#
#..#...#
########
 
Output:
3
'''
 
n, m = map(int, input().split())
array = [input() for _ in range(n)]
ways = [(-1,0), (1,0), (0, -1), (0, 1)]
visited = [[True if array[r][c] == '#' else False for c in range(m)] for r in range(n)]
rooms = 0
def DFS(i, j):
    for way in ways:
        r, c = i + way[0], j + way[1]
        if 0 <= r < n and 0 <= c < m and not visited[r][c]:
            visited[r][c] = True   #
            DFS(r, c)
 
for i in range(n):
    for j in range(m):
        if not visited[i][j]:
            visited[i][j] = True   #
            DFS(i, j)
            rooms += 1
 
print(rooms)

여기서 방의 갯수를 구하는 idea는 (i, j) 라는 좌표로 표시되는 노드에 대해 방문을 최초로 시도할 때, 방의 갯수를 카운트 하는 것이다. 왜냐면 DFS는 함수가 한 번 호출되면 연결된 모든 가능한 노드를 방문하기 때문에, 최초 호출시 (믿고) 방의 개수를 카운트하는 것이다. 바로 이 방이 connected component 이다.

한편 위 코드에서는 'visited' array를 통해 이미 방문되었는지 여부를 확인한다. 그러나 여기서 고칠 것이 있다. 바로 방문을 시도한 노드에 대해 방문여부를 체크한 뒤 '방문했음'을 표시하는 과정의 위치이다. 잘 살펴보면, 사고방식의 차이지만, DFS(i, j) 호출이 정당하면(not visited[i][j] is True) 바로 [i][j]에 대해 방문했음을 표시하면 되는 것은 맞지만, 이것은 호출된 함수인 DFS 안에 한 번만 표시해 주면 된다. 따라서 # 표시된 부분을 DFS 함수 내 맨 첫줄에 표시하면 된다. 몇 가지 코드를 간소화 할 수 있는 사항을 수정하여 다음과 같이 최종적으로 코드를 작성해 본다.

# Adapted from William Lin's code
import sys
sys.setrecursionlimit(10**6)
#sys.stdin = open('cr.txt', 'r')

n, m = map(int, input().split())
s = [[c for c in input()] for _ in range(n)]
#ways = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def e(i, j):
    # True if visitable
    return 0 <= i < n and 0 <= j < m and s[i][j] == '.'

def dfs(i, j):
    s[i][j] = '#'
    if e(i-1, j): dfs(i-1, j)
    if e(i+1, j): dfs(i+1, j)
    if e(i, j-1): dfs(i, j-1)
    if e(i, j+1): dfs(i, j+1)

rooms = 0
for i in range(n):
    for j in range(m):
        if e(i, j):
            dfs(i, j)
            rooms += 1
print(rooms)