[BOJ/BFS] 백준 4963 - 섬의 개수 (Java)

4963 - 섬의 개수

https://www.acmicpc.net/problem/4963

문제

정사각형으로 이뤄져 있는 섬과 바다 지도
한 정사각형과 가로, 세로, 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형
두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 걸어서 갈 수 있는 경로가 있어야 함
지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없음

=> 섬의 개수?

입력
여러 개의 테스트 케이스로 이뤄져 있음
각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 h가 주어짐 (w, h (양의 정수) < 50)
입력의 마지막 줄에는 0이 2개 주어짐
출력: 각 테스트 케이스에 대해서, 섬의 개수

---

풀이

• 가로, 세로, 또는 대각선으로 이동 가능

static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};

---

코드

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

// 섬의 개수
public class boj_4963 {
    static int w, h;
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
    static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};

    public static void bfs(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{x, y});
        visited[x][y] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll();

            for (int dir = 0; dir < 8; dir++) {
                int nx = cur[0] + dx[dir];
                int ny = cur[1] + dy[dir];

                if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
                if (!visited[nx][ny] && map[nx][ny] == 1) {
                    q.offer(new int[]{nx, ny});
                    visited[nx][ny] = true;
                }
            }
        }
    }

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

        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());

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

            map = new int[h][w];
            visited = new boolean[h][w];

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

            int cnt = 0;
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (!visited[i][j] && map[i][j] == 1) {
                        bfs(i, j);
                        cnt++;
                    }
                }
            }

            System.out.println(cnt);
        }
    }
}