섬의 개수

문제

1을 육지로, 0을 물로 가정한 2D 그리드 맵이 주어졌을 때, 섬의 개수를 계산하라. (연결되어 있는 1의 덩어리 개수를 구하라)

 

· 입출력 예 

grid map	return
11110 11010 11000 00000	1
11000 11000 00100 00011	3

---

풀이

1. DFS로 그래프 탐색

이와 같이 작성하였을 경우, grid를 dfs 함수 호출시마다 넘겨주어야 하고, 함수 호출 시 매번 self.가 따라 붙는다. 

 

2. DFS로 그래프 탐색 (중첩함수 사용)

DFS 탐색을 하는 dfs 함수는 동서남북을 모두 탐색하며 재귀호출한다. 이동하고자 하는 곳이 육지가 아닌 경우에 return 하도록 설정해줌으로써 연결되어 있는 섬을 구할 수 있다. 이 함수에서 이미 방문했던 곳(grid[i][j])은 1이 아닌 값으로 마킹하는데, 이를 통해 다음에 다시 계산하는 과정을 생략할 수 있다.

 

또한 여기서는 중첩 함수를 이용하여 코드를 좀 더 간결하게 작성하였다.

---

Info

1. 중첩함수는 부모 함수에서 선언한 변수도 유효한 범위 내에서 사용할 수 있다.