[Java] 백준 4963 섬의 개수

 

 

문제

섬(1)과 바다(0)로 이루어진 지도가 주어진다.

이어져 있는 섬은 하나의 섬으로 간주할 때, 섬의 총 개수를 출력해라.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class b4963 {
    static int W, H;
    static int[][] map;
    static int SEA = 0, LAND = 1, VISITED = 2;

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

        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            W = Integer.parseInt(st.nextToken());
            H = Integer.parseInt(st.nextToken());
            if (W == 0) break;

            map = new int[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 (map[i][j] == LAND) { // bfs로 이어져 있는 섬 체크
                        bfs(i, j);
                        cnt++;
                    }
                }
            }

            sb.append(cnt).append("\n");
        }

        System.out.println(sb);
    }

    static void bfs(int x, int y) {
        // 상하좌우+대각선
        int[] dx = {-1, 1, 0, 0, -1, -1, 1, 1};
        int[] dy = {0, 0, -1, 1, -1, 1, -1, 1};

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});
        map[x][y] = VISITED;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            for (int i = 0; i < 8; i++) {
                int nx = current[0] + dx[i];
                int ny = current[1] + dy[i];
                if (isRange(nx, ny) && map[nx][ny] == LAND) {// 탐색결과가 섬일 때
                    queue.add(new int[]{nx, ny});
                    map[nx][ny] = VISITED;
                }
            }
        }
    }

    static boolean isRange(int x, int y) {
        if (x < 0 || x >= H || y < 0 || y >= W)
            return false;
        return true;
    }
}

 

 

채점 결과