[백준] 4963 섬의 개수 (JAVA)

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

4963번: 섬의 개수

풀이

위의 문제는 예전에 풀었던 백준1012번과 동일하다 문제에서 갈수있는 섬의 개수를 구하라고 했는데 이는 DFS혹은 BFS로 탐색할수있는 섬들의 집합이 몇개나 있는지 물어보는 문제이다. 우선 상하좌우 대각선으로 갈수있는 집합을 만들어주고 그다음 BufferdReader로 읽어서 visit와 map을 초기화 시켜준다. 그 이후 만약 현재 위치가 바다가 아닌 섬이고 미방문한 지역중 섬인 지역이 있으면 그곳에서 다시 DFS를 해준다.

사실 이문제는 크게 어려운 문제가 아닌 그저 DFS를 수행할줄 알면 간단히 풀수있는 문제였다.

코드는 아래에 적어놓겠다.

import java.io.*;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    static int[][] map;
    static boolean[][] visit;
    static int[] dr_x = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dr_y = {0, 1, 1, 1, 0, -1, -1, -1};
    static int count = 0;
    static int h;
    static int w;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st ;

        while(true){
//            w = sc.nextInt();
//            h = sc.nextInt();
            st = new StringTokenizer(br.readLine(), " ");
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());
            if(h==0 && w==0)
                break;

            map = new int[h][w];
            visit = new boolean[h][w];
            count = 0;

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

            for(int i=0; i<h; i++){
                for(int j=0; j<w; j++){
                    if(map[i][j] == 1 && visit[i][j] == false){
                        visit[i][j]=true;
                        DFS(i, j);
                        count++;
                    }
                }
            }
//            System.out.println(count);
            bw.write(String.valueOf(count) + "\n");
        }
        bw.flush();
        bw.close();
    }

    //현재 좌표는
    public static void DFS(int x, int y){
        for(int d=0; d<8; d++){
            int nx = x + dr_x[d];
            int ny = y + dr_y[d];
            if(nx>=0 && nx<h && ny>=0 && ny<w)
                if(map[nx][ny]==1 && visit[nx][ny]==false) {
                    visit[nx][ny] = true;
                    DFS(nx, ny);
                }
        }
    }
}