[백준] 4963번: 섬의 개수

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

---

import java.util.Scanner;

public class Baekjoon4963 {
    public static int[][] map;
    public static int w;
    public static int h;
    public static int count;
    public static int[] move = {-1, 0, 1};
    public static void main(String[] args)  {
        Scanner scanner = new Scanner(System.in);

        while(true) {
            w = scanner.nextInt();
            h = scanner.nextInt();
            if(w == 0 && h == 0) {
                break;
            }
            map = new int[h][w];

            count = 0;

            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    map[i][j] = scanner.nextInt();
                }
            }

            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (map[i][j] == 1) {
                        go(i, j);
                        count++;
                    }
                }
            }

            System.out.println(count);
        }
    }
    public static void go(int m, int n) {
        for (int k : move) {
            for (int i : move) {
                if(k == 0 && i == 0) {
                    continue;
                }
                int dh = m;
                int dw = n;
                dh += k;
                dw += i;
                if (dw >= 0 && dh >= 0 && dw < w && dh < h && map[dh][dw] == 1) {
                    map[dh][dw] = 0;
                    go(dh, dw);
                }
            }
        }
    }
}

델타 탐색의 확장이다. 상하좌우 뿐만 아니라 대각선도 포함해야 되는 경우이다.

 

왼쪽 위부터 시계방향으로 진행하면 델타배열을 작성하기 쉬워진다.

 

(-1, -1), (-1, 0), (-1, 1)

(0, -1), (0, 0), (0, 1)

(1, -1,), (1, 0), (1, 1)

순서로 [-1, 0, -1]의 1차원 배열을 2중 for문을 이용해 탐색을 하면 된다.

 

(0, 0)은 자기 자신이라 탐색을 할 필요가 없다.