섬의 크기를 입력받고, map을 입력받은 뒤, 1은 섬, 0 은 바다라 가정한다.
섬에서는 상, 하, 좌, 우, 네방향의 대각선을 포함하여 총 8가지의 이동경로를 가질 수 있다.
하지만, 바다인 경우에는 움직일 수 없다.
즉, 0, 0 위치부터 섬을 찾은 후, 움직일 수 있는 위치까지 모두 방문한 뒤 방문 여부를 기록하면 섬을 중복하여 셀 경우를 피할 수 있고, 방문하지 않은 섬을 새로 발견할 경우 같은 방식으로 진행하면 지도의 모든 섬의 수를 셀 수 있다.
섬을 발견한 경우 깊이 우선 탐색을 이용하여, 갈 수 있는 모든 섬을 방문한 뒤 기록하는 방식으로 문제를 푸는 것이다.
다음은 Java로 작성한 코드이다.
import java.util.ArrayList;
import java.util.Scanner;
public class Island {
static int[][] metrix;
static boolean[][] visited;
static int row;
static int column;
static int[] moveX = {-1, -1, -1, 0, 0, 1, 1, 1};
static int[] moveY = {-1, 0, 1, -1, 1, -1, 0, 1};
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//가로, 세로 입력
row = scan.nextInt();
column = scan.nextInt();
//섬의 개수
int count = 0;
//정답저장 리스트
ArrayList<Integer> solution = new ArrayList<Integer>();
//입력값이 0,0 이 아니면 반복
while(row != 0 && column != 0 ) {
//섬의 지도, 방문 여부 배열
metrix = new int[column][row];
visited = new boolean[column][row];
//입력 및 초기화
for (int i = 0; i < column; i++) {
for (int j = 0; j < row; j++) {
metrix[i][j] = scan.nextInt();
visited[i][j] = false;
}
}
//1인 칸 중 방문한 적이 없으면 새로운 섬이라 판단
for (int i = 0; i < column; i++) {
for (int j = 0; j < row; j++) {
if(metrix[i][j]==1) {
if(!visited[i][j]) {
count++;
dfs(i,j);
}
}
}
}
//섬의 개수 저장 및 초기화
solution.add(count);
count = 0;
row = scan.nextInt();
column = scan.nextInt();
}
//출력
for(int s : solution) {
System.out.println(s);
}
}
public static void dfs(int x, int y) {
//방문한적이 있다면 return
if(visited[x][y]) {
return;
}
//방문 표시
visited[x][y] = true;
//해당 위치에서 움직일 수 있는 위치 깊이 우선 탐색
for (int i = 0; i < 8; i++) {
int xx = x + moveX[i];
int yy = y + moveY[i];
if(xx >= 0 && yy >= 0 && xx < column &&yy < row) {
if(metrix[xx][yy]==1) {
dfs(xx, yy);
}
}
}
}
}
몇 개의 지도가 입력 될 지 모르기 때문에 solution을 저장하는 ArrayList를 만들어서 사용했고, 하나의 지도에 대한 처리를 모두 완료했다면, 다시 입력받아 진행하게 하였다.
처음에 8방향으로 이동할 때, 배열의 인덱스에 대한 문제가 있었는데 덧셈이 조건을 만족하지 못하면, 진행하지 않게
하여 해결하였다.
