[DFS] Number of Islands

1을 섬, 0을 물이라고 할때 섬의 갯수를 구하라는 문제이다

섬끼리는 adjacent되어 있다

 

예시로 설명을 해보자면, 이렇게 동서남북이 물에 의해 끊기지 않는 덩어리의 갯수를 구하라는 뜻이다.

이러한 문제는 DFS로 풀어낼 수 있다.

DFS는 기본적으로 stack을 하나 두고, 방문전 node들을 모두 false로 둔다

이후 방문한 node에 대해 true로 바꾸고, 방문한 node와 인접한 node들을 모두 stack에 담는다.

stack 에 담긴 node에 하나씩 접근하는데, 이때 node의 로직처리를 스택의 순서대로 한다.

 

예시를 들어보자면 다음과 같다.

DFS를 하면 해당 그래프는 우측상단의 순서대로 순회가 될 텐데, 그 과정에서 stack과 array의 변화를 일부 살펴보면 아래와 같다.

방문하는 node를 stack에 넣고, 방문이 끝난 node는 stack에서 뺀다. 이때 특정 node에 다다르면 방문 예정인 node는 해당 node와 adjacent한 node들이다.

 

DFS에 대한 함수는 다음과 같다.

node가 1인 경우만 순회를 지속하며, 순회를 하면 0으로 바꿔주고 인접 node를 순회한다.

여기에서는 stack을 이용하지 않았다.

 

실제 로직은 다음과 같다.

1을 만나는 순간 counter를 올린다.

이후 dfs를 사용하여 순회를 시작한다. dfs로직에 의해 인접 1이 모두 0으로 바뀌면 순회가 종료된다.