백준 4963번: 섬의 개수 (JAVA) <BFS / DFS>

 

문제 해석

 

지도가 주어진다. 1은 땅, 0은 바다이다. 사람이 있다 가정하면 사람은 상하좌우, 대각선으로 이동할 수 있고 땅 다음 땅을 밟으면 이어진 땅으로 간주해 섬으로 여기지 않는다. 테스트 케이스마다 섬의 개수를 구해야 한다.

 

알고리즘

 

BFS 또는 DFS를 이용하여 현재 위치를 계속 바꿔주며 연이어 이동할 수 있는 땅인지 확인한다.

 

코드

 

BFS

 

지도를 저장할 2차원 배열, 상하좌우/대각선 이동을 의미하는 배열 X와 Y를 선언한다.

현재의 위치를 나타내는 클래스 Node를 정의한다.

 

 

w와 h가 0이면 프로그램을 종료한다.

지도에 있는 모든 인덱스를 탐색하는데 해당 인덱스가 0이 아닌 값을 가질 때는 땅이므로 섬의 개수를 추가하고 BFS를 실행한다.

 

 

현재 위치를 Queue에 넣어주고 현재 위치를 지도에서 0으로 바꿔준다. 또한 현재 위치를 이용해 인접 노드를 모두 탐색할 때 인접 노드 중에 1(땅)이 있으면 해당 노드가 위치하는 인덱스를 0으로 바꿔 재탐색하는 경우가 없게 한다.

 

DFS

 

 

방문 여부를 체크하는 배열을 만든다.

 

 

현재 위치 인덱스를 방문한 것으로 표시하고 인접노드 중에 1(땅)이고 방문하지 않은 인덱스가 있으면 해당 위치에서 재귀 실행한다.