ch12-1(leetcode 200). 섬의 개수

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

 

leetcode 200번 ( https://leetcode.com/problems/number-of-islands/ )

 

풀이 1. 

그래프 탐색 방법 중 DFS를 이용해서 풀 수 있다. DFS와 BFS는 그래프 중 connected components 문제를 푸는 데도 사용된다. 이 문제도 점 하나가 사방의 주변 점과 연결되면 연결된 육지로, 사방이 물이면 개별적인 섬으로 간주하기 때문에 connected component의 개수를 찾는 문제로 볼 수 있다. 

 

또한 입력이 주어지면 다른 제약 사항이 없는 한 입력을 임의로 바꿔서 풀 수도 있었다. 

이 방법에서는 for loop를 2번 사용해서 입력으로 주어진 grid를 행과 열로 탐색해서 육지(grid[i][j]==1)를 찾는다. 그리고 찾은 육지 위치에 대해 dfs를 실행한다. 

 

dfs 함수는 재귀적으로 실행되어야 하므로 solution 함수 안의 또 다른 함수(내부 함수)로 선언한다. 

내부 함수로 선언된 dfs() 함수는 solution 함수에서 선언된 지역 변수들의 값을 가져오거나 변경할 수 있어서 재귀 방식을 사용할 때 많이 사용된다. 

 

dfs 함수에서는 우선 해당 위치가 유효한지(해당 위치가 물인지, 가로와 세로가 grid의 범위에서 벗어나지 않았는지)를 확인한 다음에 그 위치의 값을 육지에서 물로 바꾼다(1->0). 그리고 그 위치를 기준으로 동서남북으로 dfs 탐색을 진행하면서 사방의 육지를 물로 바꾼다.

 

만약 육지가 여러 개가 아니고 하나였다면 for loop에서 한 번의 dfs() 호출로 모든 육지가 물로 바뀔 것이다. 이 경우 값은 1이다. 

또는 만약 육지가 아예 없었다면 for loop에서 육지를 찾을 수 없으므로 count가 증가하지 않아서 육지의 개수는 0이 될 것이다. 

 

다음 그림은 leetcode의 예제 1번을 그림으로 표현한 것이다. 검정색 점은 육지이고 파란색 점은 물이다. 

for loop로 육지를 탐색한다면 grid[0][0]인 맨 위의 점에 대해서 맨 먼저 dfs() 함수가 호출될 것이다. 

 

 

dfs()가 호출된 경우 해당 위치가 유효한지를 먼저 판단한 뒤, 유효하면 해당 위치의 값을 육지에서 물로 바꾼다.

교재에서 제시한 dfs() 함수에서는 남->북->동->서 방식으로 탐색을 진행하므로, 그 다음엔 한 칸 아래에 있는 점에 대해서 dfs()를 다시 호출한다. 

 

 

dfs()가 계속 호출되면서 아래 그림처럼 모든 점이 육지에서 물로 바뀐다. 

 

 

해당 예시에서는 육지가 1개였으므로 모든 점이 물이 되지만, 육지가 여러 개일 경우 검정 점이 남아있다. 

현재는 (4, 2)에서 dfs()가 동작하지만 이제 사방의 모든 점이 물이므로 dfs()를 더 이상 호출하지 않고 해당 점을 기준으로 호출된 dfs()는 종료될 것이다. 

 

 

그러면 해당 점을 호출하기 전의 위치인 (4, 1)에서 다시 남은 dfs() 코드가 실행될 것이다.

하지만 사방의 모든 점이 물이므로 해당 점에서의 dfs()는 종료될 것이며, (4, 1)을 기준으로 dfs()를 호출한 이전 위치의 dfs() 실행 지점으로 돌아갈 것이다. 

 

이렇게 맨 처음 dfs()를 호출한 (1, 1)에서도 dfs()가 종료되면 (0, 0)이 속한 육지를 물로 바뀌었으니 육지 count가 1 증가한다. 

그리고 for loop가 다시 실행되어 남은 점들에 대해서 육지가 있는지 탐색할 것이다. 하지만 남은 육지가 없으므로 1을 리턴하게 된다.