[leetcode][200] Number of Islands

문제 : https://leetcode.com/problems/number-of-islands/

---

2차원 배열 grid가 있다. grid는 1(육지)이나 0(물)로 이루어져있다.

연결되어 있는 1들의 테두리가 모두 0들로 둘러쌓여 있다면 이를 하나의 육지로 본다.

grid의 테두리도 0으로 감싸여있다고 한다.

grid에 있는 육지의 수를 구해라.

---

DFS, BFS 연습하기 좋은 문제다.

기본적인 구현으로도 풀 수 있다.

grid를 전부 탐색하면서 육지를 발견하면 해당 위치를 기준으로 dfs나 bfs를 돌린다.

이 때, 육지를 발견했으므로 정답에 1을 더해준다.

돌리면서 4방면(상하좌우)의 grid 요소들을 탐색하며 이가 육지(1)인 경우 물이나 육지 이외의 사인으로 바꾸어 탐색한 위치라고 표시한다. (연결된 육지는 하나로 보기 때문. 탐색한 grid 좌표를 다시 탐색하는 것을 방지하기 위함) 

 

시간복잡도는 grid가 N x M일 때, O(NM)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/200.%20Number%20of%20Islands.cpp

---

아주 정석적인 DFS, BFS 구현 문제라 문제 난이도가 medium이라고 되어있는데 easy에 더 가까운 듯 하다.

코드는 간단하게 DFS, 재귀로 구현했다.