문제

이해

어제 풀었던 안전 영역 (문제 번호: 2468) 과 같은 문제이다.

검은 타일은 땅을 의미하고 흰 타일은 바다를 의미한다.

지도가 주어졌을 때 섬의 개수를 세면 된다.

섬은 가로, 세로, 대각선으로 연결되어 있는 땅을 의미한다.

접근

풀이 방법은 안전 영영과 같이 각 테스트 케이스에서 2차원 배열을 순회하면서 땅을 발견하면 현 위치를 기준으로 BFS를 수행하면 된다.

단, BFS를 수행할 때 문제에서 섬은 대각선까지 연결되어 있다는 조건이 있기 때문에 대각선 방향까지 같은 깊이에서 탐색해야 한다.

이 점만 유의하면 똑같은 문제이다.

코드

package java_baekjoon;

import java.io.*;
import java.util.*;

public class prob4963 {
    static int w;
    static int h;
    static int[][] square;
    static int[] d_row = { -1, 0, 1, -1, 0, 1, -1, 0, 1 };
    static int[] d_col = { -1, -1, -1, 0, 0, 0, 1, 1, 1 };

    static class xy {
        int x;
        int y;

        public xy(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while (true) {
            int cnt = 0;
            Queue<xy> q = new LinkedList<>();
            StringTokenizer st = new StringTokenizer(br.readLine());

            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());

            if (w == 0 && h == 0) {
                break;
            }

            square = new int[h][w];
            for (int i = 0; i < h; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < w; j++) {
                    square[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (square[i][j] == 1) {
                        cnt++;
                        q.add(new xy(i, j));
                        square[i][j] = 0;
                    }

                    while (!q.isEmpty()) {
                        xy cur = q.poll();

                        for (int k = 0; k < 9; k++) {
                            int new_row = cur.x + d_row[k];
                            int new_col = cur.y + d_col[k];

                            if(new_row >= 0 && new_row < h && new_col >= 0 && new_col < w && square[new_row][new_col] == 1){
                                q.add(new xy(new_row, new_col));
                                square[new_row][new_col] = 0;
                            }
                        }
                    }
                }
            }
            System.out.println(cnt);
        }
    }
}

결과