[BOJ 4963] 섬의 개수 (Java, 격자형 그래프 탐색)

---

문제 링크

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

4963번: 섬의 개수

---

풀이

- 전형적인 격자형 그래프 탐색 문제

- 테스트 케이스별로 초기화 및 섬의 개수 카운팅 수행

- 정점에서 움직일 수 있는 방향은 8가지 (상하좌우, 대각선 양방향)

- N은 최대 50

- 시간 복잡도 : O(N^2) , 테스트 케이스별로 O(2500) 씩 걸림

 

w, h 입력 값이 조금 헷갈리고, 테스트 케이스 처리만 번거로웠지 나머지는 그래프 탐색 기본 유형과 동일했음

---

제출 코드

 

BFS 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
 
    static StringBuilder sb = new StringBuilder();

    static int W, H, CNT;

    static int[][] MAP;

    static boolean[][] VISIT;

    static int[][] DIRECTION = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}};

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String str = "";
        while(!(str = br.readLine()).equals("0 0")) {
            StringTokenizer st = new StringTokenizer(str);
            W = Integer.parseInt(st.nextToken());
            H = Integer.parseInt(st.nextToken());

            MAP = new int[H][W];
            VISIT = new boolean[H][W];

            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());
                }
            }

            CNT = 0;
            pro();
        }

        System.out.println(sb);
        br.close();
    }

    static void bfs(int startX, int startY) {
        Queue<Integer> que = new LinkedList<>();
        que.add(startX);
        que.add(startY);
        VISIT[startX][startY] = true;

        while(!que.isEmpty()) {
            int x = que.poll(), y = que.poll();

            for(int i = 0; i < 8; i++) {
                int nx = x + DIRECTION[i][0];
                int ny = y + DIRECTION[i][1];

                if(nx < 0 || ny < 0 || nx >= H || ny >= W) continue;
                if(VISIT[nx][ny]) continue;
                if(MAP[nx][ny] == 0) continue;

                que.add(nx);
                que.add(ny);
                VISIT[nx][ny] = true;
            }
        }
    }

    static void pro() {
        for(int i = 0; i < H; i++) {
            for(int j = 0; j < W; j++) {
                if(!VISIT[i][j] && MAP[i][j] == 1) {
                    CNT += 1;
                    bfs(i, j);
                }
            }
        }

        sb.append(CNT).append("\n");
    }

    public static void main(String[] args) throws Exception {
        input();
    }
}