Python 알고리즘 인터뷰 - 문제 32. 섬의 개수

leetcode 200. Number of Islands - https://leetcode.com/problems/number-of-islands/description/

 

1을 육지로, 0을 물로 가정한 2D 그리드 맵이 주어졌을 때, 섬의 개수를 계산하라.

(연결되어 있는 1의 덩어리 개수를 구하라)

 

예제1

입력

11110

11011

11000

00000

 

출력

1

 

예제2

입력

11000

11000

00100

00011

 

출력

3

 

풀이

솔직히 DFS를 사용해서 풀이를 진행하는데 왜 DFS인지는 이해하기가 힘들다. 기본 DFS의 경우 연결된 vertex와 edge를 기반으로 자료구조가 구성되어 있는데 이 문제의 경우에는 2차원 배열이기 때문이다. 다만 동서남북이 모두 연결된 그래프이다. 이전에는 단방향 그래프만 가정했는데 이제는 양방향 연결 그래프라고 생각하면 된다.

 

DFS라는 개념은 잠시 배제하고 로직을 찬찬히 들여다보면서 풀이한다.

 

다음과 같은 2차원 배열이 있다고 했을 때 노란색으로 칠해져있는 부분은 그래프 자료구조로 바라 볼 때 '1'로 표기된 배열의 좌표(i, j)가 vertex이고 해당 동서남북에 위치하는 좌표의 값이  '1'인 경우 존재하는 경우 '연결'되었다고 볼 수 있다.

 

이렇게 연결된 그래프를 순회하도록 한다. 순회 방향의 우선 순위는 동,서,남,북으로 진행하며, 순회한 좌표의 값을 0으로 설정한다. 해당 코드를 구현하면 다음과 같다. 

def dfs(grid, i, j):
	if i < 0 or i >= len(grid) or
    	j < 0 or j >= len(grid[0]) or
        grid[i][j] == 0:
       	return
     
     grid[i][j] = 0
     
     dfs(grid, i+1, j)
     dfs(grid, i-1, j)
     dfs(grid, i, j+1)
     dfs(grid, i, j-1)

좌표의 위치에서 벗어났거나 해당 좌표값이 0이면 순회를 진행하지 않는다. 좌표의 위치에서 벗어나지 않고 grid[i][j]가 1인 경우 0으로 변경한다. 이를 DFS 상에서 해당 vertex가 discovered 되었다고 볼 수 있다. 이 후 동,서,남,북 방향으로 순회를 하여 '연결'된 좌표의 값이 모두 0이 될 때까지 반복한다.

위의 그림에서 dfs(grid, 0, 0)을 호출할 경우 진행사항은 다음과 같다.

먼저 동쪽(i+1) 방향으로 이동하면서 값을 0으로 변경한다. 더 이상 오른쪽에 연결이 되어 있지 않으면 함수를 반환하고 서쪽(i-1)로 이동한다.

 

서쪽으로 이동하려고 했으나 이미 0으로 변경(discovered)되어 있다. 따라서 남쪽(j+1)으로 이동한다.

다시 동쪽으로 이동을 한다. 이동된 위치 (2,1)에서는 동,서,남,북 모두 연결되지 않았거나 discovered되어 있으므로 (1,1)에서 다시 순회를 진행한다. 

서쪽으로 이동한다. 해당 위치에서도 동,서,남,북이 연결되어 있지 않으므로 (1,1)로 돌아온다.

마지막으로 남쪽으로 이동한다. 이후 모든 연결이 종료되었으므로 재귀함수는 모두 반환한다.

다음과 같이 순회를 완료하면 섬의 개수가 1개 증가된다. dfs함수 호출 이후 count를 1 증가 시킨다.

dfs(grid, i, j)
count += 1

섬의 개수를 세기 위해 grid를 가로, 세로 방향으로 순회하며 grid[i][j]가 1인경우 dfs함수를 호출하여 연결을 확인한 후 count를 증가시킨다. 코드는 다음과 같다.

count = 0
for i in range(len(grid)):
	for j in range(len(grid[0]):
		if grid[i][j] == 1:
        	dfs(grid, i, j)
            count += 1

 

전체 코드는 다음과 같다.

def numIslands(grid):
    def dfs(grid, i, j):
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == '0':
            return

        grid[i][j] = '0'
        dfs(grid, i + 1, j)
        dfs(grid, i - 1, j)
        dfs(grid, i, j + 1)
        dfs(grid, i, j - 1)

    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                dfs(grid, i, j)
                count = count + 1

    return count