[백준 4963, Java] 섬의 개수

문제

www.acmicpc.net/problem/4963

4963번: 섬의 개수

풀이

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Land{
    int x;
    int y;

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

public class Main {
    public static int[][] map;
    public static boolean[][] visited;
    public static int W;
    public static int H;
    public static final int LAND = 1;
    public static final int SEA= 0;

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

    public static  int numberOfIsland = 0;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        while(true){
            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 h = 0; h<H; h++){
                st = new StringTokenizer(br.readLine()," ");
                for(int w = 0 ;w<W ;w++){
                    map[h][w] = Integer.parseInt(st.nextToken());
                }
            }

            //순회
            numberOfIsland = 0;
            for(int h = 0; h<H; h++){
                for(int w = 0 ;w<W ;w++){
                    if(!visited[h][w] && map[h][w] == LAND){
                        ++ numberOfIsland;
                        getIslandBoundaryByBfs(h, w);
                    }
                }
            }
            bw.write(String.valueOf(numberOfIsland)+"\n");
        }
        bw.flush();

    }
    
        //(x,y)를 포함하는 섬 표시 - > (x,y)가 섬이라는 보장이 없는 경우
    public static void getIslandBoundaryByDfs(int x, int y){
        if(x<0 || y<0 || x>=H || y>=W){
            return;
        }
        else if(map[x][y]==SEA){
            return;
        }
        else if(visited[x][y]){
            return;
        }
        else{
            visited[x][y] = true;
            for(int d= 0 ;d<8; d++){
                int nx = x + dx[d];
                int ny = y + dy[d];

                getIslandBoundaryByDfs(nx, ny);
            }
        }
    }

    //(x,y)를 포함하는 섬 표시 -> (x,y)가 섬이라는 보장이 있는 경우
    public static void getIslandBoundaryByDfs(int x, int y){
        visited[x][y] =true;

        for(int d= 0 ;d<8 ;d++){
            int nx = x + dx[d];
            int ny = y + dy[d];

            if(nx>=0 && ny>=0 && nx<H && ny< W){
                if(map[nx][ny]==LAND && !visited[nx][ny]){
                    getIslandBoundaryByDfs(nx, ny);

                }
            }
        }
    }

    //
    public static void getIslandBoundaryByBfs(int x, int y){
        //초기화
        Queue<Land> queue = new LinkedList<>();
        Land land = new Land(x, y);
        queue.add(land);
        visited[x][y] = true;

        while (!queue.isEmpty()){
            Land currentLand = queue.poll();

            for(int d= 0 ;d<8; d++){
                int nx = currentLand.x + dx[d];
                int ny = currentLand.y + dy[d];

                if(nx>=0 && ny>=0 && nx<H && ny<W){
                    if(map[nx][ny]==LAND && !visited[nx][ny]){
                        queue.add(new Land(nx, ny));
                        visited[nx][ny] =true;
                    }
                }
            }
        }

    }
}