Q. 4963 자바 : 섬의 개수

Q. 4963 자바 : 섬의 개수

 

문제 : boj.kr/4963

실버 2 난이도의 문제이다.

 

격자 그래프가 주어졌을 때 이를 DFS, BFS로 순회하고 결과를 출력하는 문제이다.

주의해야 할 점은 순회 방향이 상 하 좌 우 + 대각선을 포함한다

그래서 탐색을 위한 dy, dx의 크기를 8로 늘리고 대각선 4방향을 추가해줬다.

 

그래프의 크기 W, H가 중지므로 시간복잡도는 아래와 같다.

1. DFS or BFS 순회 - O(W * H)

이 때 W, H의 최대값은 50이므로 시간초과는 걱정하지 않아도 된다.

그래프의 자료형은 boolean 2차원 배열로 해결했다.

 

풀이는 아래와 같다.

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

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

    static int W, H;
    static boolean[][] graph;

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

    static void input() {

        graph = new boolean[H + 1][W + 1];

        for (int i = 1; i <= H; i++) {
            for (int j = 1; j <= W; j++) {
                if (scan.nextInt() == 1) graph[i][j] = true;
            }
        }
    }

    static void dfs(int y, int x) {

        graph[y][x] = false;
        for (int i = 0; i < 8; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny == 0 || nx == 0 || ny == H + 1 || nx == W + 1) continue;
            if (graph[ny][nx]) dfs(ny, nx);
        }
    }

    static void bfs(int y, int x) {

        Queue<int[]> que = new LinkedList<>();
        graph[y][x] = false;
        que.add(new int[] {y, x});

        while (!que.isEmpty()) {

            int[] point = que.poll();
            for (int i = 0; i < 8; i++) {
                int ny = point[0] + dy[i];
                int nx = point[1] + dx[i];
                if (ny == 0 || nx == 0 || ny == H + 1 || nx == W + 1) continue;
                if (graph[ny][nx]) {
                    que.add(new int[] {ny, nx});
                    graph[ny][nx] = false;
                }
            }
        }
    }

    static void pro() {

        int cnt = 0;
        for (int i = 1; i <= H; i++) {
            for (int j = 1; j <= W; j++) {
                if (graph[i][j]) {
                    cnt++;
                    bfs(i, j);
                    //dfs(i, j);
                }
            }
        }
        System.out.println(cnt);
    }

    public static void main(String[] args) {

        while (true) {
            W = scan.nextInt();
            H = scan.nextInt();
            if (W == 0 && H == 0) break;
            input();
            pro();
        }
    }


    static class FastReader {
        // BufferedReader의 빠른 속도, 
        // + Scanner의 타입별 입력값을 받는 기능을 혼합
        // (자바 내부에 구현된 Scanner는 속도가 느림)
        // 다른분의 코드를 참고한 코드
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}