[99클럽 코테 스터디 6일차 TIL] 섬의 개수

 

6일차 문제

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

 

 

 

문제 풀이

기본적인 bfs 문제

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

public class Main {

    static int[][] arr;
    static boolean[][] visited;
    static int[] dx = {0, 0, 1, -1, -1, 1, -1, 1};
    static int[] dy = {1, -1, 0, 0, -1, 1, 1, -1};

    static int w;
    static int h;

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

        while(true) {
            st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());
            int answer = 0;

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

            arr = new int[h][w];
            visited = new boolean[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());
                }
            }

            for(int i=0; i<h; i++) {
                for(int j=0; j<w; j++) {
                    if(arr[i][j] == 1 && !visited[i][j]) {
                        answer++;
                        bfs(i, j);
                    }
                }
            }
            System.out.println(answer);
        }
    }

    private static void bfs(int i, int j) {
        Queue<int[]> q = new LinkedList<>();

        q.add(new int[] {i, j});
        visited[i][j] = true;

        while(!q.isEmpty()) {
            int[] now = q.poll();
            for(int k=0; k<8; k++) {
                int nextX = now[0] + dx[k];
                int nextY = now[1] + dy[k];

                if(nextX>=0 && nextX<h && nextY >=0 && nextY<w) {
                    if(arr[nextX][nextY] == 1 && !visited[nextX][nextY]) {
                        q.add(new int[] {nextX, nextY});
                        visited[nextX][nextY] = true;
                    }
                }
            }
        }
    }
}