[JAVA] 백준 4963번- 섬의 개수

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

4963번: 섬의 개수

 

 

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

class Point {
    int x, y;

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

public class Main {
    static int[][] arr;

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

    static Queue<Point> q = new LinkedList<>();

    public static void bfs(int x, int y) {
        q.add(new Point(x, y));

        while (!q.isEmpty()) {
            Point p = q.poll();
            for (int i = 0; i < 8; i++) { // 8방향으로 탐색
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];

                if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;

                if (arr[nx][ny] == 1) { // 땅이면
                    arr[nx][ny] = 0; // 방문 처리
                    q.add(new Point(nx, ny));
                }

            }
        }

    }

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

            StringTokenizer st;
            st = new StringTokenizer(br.readLine());

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

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

            arr = new int[h][w];

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

            int cnt = 0;
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (arr[i][j] == 1) { // 땅이면
                        cnt++; // 카운트
                        bfs(i, j);
                    }
                }
            }
            sb.append(cnt + "\n");
        }
        System.out.println(sb);
    }
}

 

 

bfs로 풀었다. 

따로 visit 배열을 안만들고 방문했을 때 0으로 바꿔 재방문을 못하도록 했다.