[BOJ] 4963 JAVA

문제

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

 

코드

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

public class Main {

    public static int w;
    public static int h;

    public static int[][] map;
    public static boolean[][] visited;

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

        while(true){
            // [input]
            // 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다.
            StringTokenizer st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());

            // 입력의 마지막 줄에는 0이 두 개 주어진다.
            if(w==0 && h==0) break;

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

            // map 저장
            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());
                }
            }

            // [solution]
            int answer = 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);
                        answer++;
                    }
                }
            }
            sb.append(answer).append('\n');
        }
        br.close();

        // [output]
        System.out.println(sb);
    }

    public static boolean CanGo(int x, int y){
        // 범위를 범어난 접근
        if(x<0 || x>=h || y<0 || y>=w) return false;
        // 이미 방문한 곳 || 바다
        if(visited[x][y] || map[x][y]==0) return false;

        return true;
    }
    
    public static void BFS(int x, int y){
        // 8방향
        // 좌상 상 우상 우 우하 하 좌하 좌
        int[] dx = {-1, -1, -1, 0, 1, 1, 1, 0};
        int[] dy = {-1, 0, 1, 1, 1, 0, -1, -1};

        Queue<Coord> queue = new ArrayDeque<>();
        queue.offer(new Coord(x, y));
        visited[x][y]=true;

        while(!queue.isEmpty()){
            Coord curr = queue.poll();
            for (int dir = 0; dir < 8; dir++) {
                int nx = curr.x +dx[dir];
                int ny = curr.y +dy[dir];
                if(CanGo(nx, ny)){
                    visited[nx][ny] =true;
                    queue.offer(new Coord(nx, ny));
                }
            }
        }
    }

    public static class Coord{
        int x;
        int y;

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