백준 4963 - 섬의 개수

Java

4963 번 - 섬의 개수

문제

접근 방법

0,0 부터 n - 1, m - 1 까지 좌표를 탐색하며, 방문하지 않았고, 섬일 경우 BFS로 근처의 갈 수 있는 모든 섬을 탐색한다. 만약 각 섬을 탐색할 때마다(BFS 탐색할 때 마다) 개수를 증가하여 총 섬의 개수를 센다.

코드

import java.util.*;
import java.io.*;

public class Main {
    static int n,m;
    static int[][] map;
    static boolean[][] vis;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        

        StringBuilder sb = new StringBuilder();

        while(true){
            StringTokenizer stk = new StringTokenizer(br.readLine());
            int cnt = 0;
            m = stoi(stk.nextToken());  // 너비
            n = stoi(stk.nextToken());  // 높이
            if(n == 0 && m == 0)
                break;

            map = new int[n][m];    
            vis = new boolean[n][m];

            for(int i = 0; i < n; i++) {
                stk = new StringTokenizer(br.readLine());
                for(int j = 0; j < m; j++) {
                    map[i][j] = stoi(stk.nextToken());
                }
            }

            for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    if(map[i][j] == 1 && !vis[i][j]) {
                        BFS(i,j);
                        cnt++;
                    }
                }
            }

            sb.append(cnt).append("\n");
        }
        
        System.out.print(sb.toString());
    }
    static int[] dy = {1,1,1,0,0,-1,-1,-1};
    static int[] dx = {-1,0,1,-1,1,-1,0,1};

    private static void BFS(int y, int x) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {y,x});

        int ny, nx;
        while(!queue.isEmpty()){
            int[] q = queue.poll();
            for(int i = 0; i < 8; i++) {
                ny = q[0] + dy[i];
                nx = q[1] + dx[i];
                if(isIn(ny, nx) && !vis[ny][nx] && map[ny][nx] == 1) {
                    vis[ny][nx] = true;
                    queue.add(new int[] {ny,nx});
                }
            }
        }
    }

    static boolean isIn(int y, int x){
        if(0 <= y && y < n && 0 <= x && x < m)
            return true;

        return false;
    }

    static int stoi(String str){
        return Integer.parseInt(str);
    }
}