[백준 4963 java 자바] 섬의 개수 (BFS/DFS)

[Silver II] 섬의 개수 - 4963

문제 링크

성능 요약

메모리: 14792 KB, 시간: 136 ms

분류

그래프 이론(graphs), 그래프 탐색(graph_traversal), 너비 우선 탐색(bfs), 깊이 우선 탐색(dfs)

문제 설명

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

---

코드

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


public class Main {
    static String[] strs;
    static int w,h = 0;
    static int[] nX = {-1, 1, 0, 0, -1, -1, 1, 1};
    static int[] nY = {0, 0, -1, 1, -1, 1, -1, 1};
    static int[][] graph;
    static class Node{
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        strs = br.readLine().split(" ");
        w = Integer.parseInt(strs[0]);
        h = Integer.parseInt(strs[1]);

        while (w != 0 && h != 0) {
            graph = new int[h][w];
            int sumCnt = 0;
            //지도 초기화
            for (int i = 0; i < h; i++) {
                strs = br.readLine().split(" ");
                for (int j = 0; j < w; j++) {
                    graph[i][j] = Integer.parseInt(strs[j]);
                }
            }
            //bfs 수행
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (graph[i][j] != 0) {
                        sumCnt++;
                        bfs(i, j);
                    }
                }
            }

            sb.append(sumCnt + "\n");

            strs = br.readLine().split(" ");
            w = Integer.parseInt(strs[0]);
            h = Integer.parseInt(strs[1]);
        }
        System.out.println(sb.toString());
    }

    static void bfs(int x, int y) {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x, y));
        graph[x][y] = 0;
        while (!q.isEmpty()) {
            Node node = q.poll();
            //8방 돌면서 link되어있는지 체크
            for (int i = 0; i < nX.length; i++) {
                int nextX = nX[i] + node.x;
                int nextY = nY[i] + node.y;
                if(nextX < 0 || nextX >= h || nextY < 0 || nextY >= w) continue;
                if (graph[nextX][nextY] == 1) {
                    graph[nextX][nextY] = 0;
                    q.offer(new Node(nextX, nextY));
                }
            }
        }
    }
}

---

코드 분석

변수선언

    static String[] strs;//입력을 BufferedReader로 받아 쪼개쓰기 위해 strs
    static int w,h = 0;//전체 섬의 높이, 너비
    static int[] nX = {-1, 1, 0, 0, -1, -1, 1, 1};//기준 좌표에서 사방팔방의 좌표 
    static int[] nY = {0, 0, -1, 1, -1, 1, -1, 1};
    static int[][] graph;//case별 전체 지도
    static class Node{//Queue에 담기 위해 지도의 좌표를 담는 Node
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }

    }

기본 Main

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));//입력받기
        StringBuilder sb = new StringBuilder();//출력을 위한 sb
        strs = br.readLine().split(" ");
        w = Integer.parseInt(strs[0]);//최초 입력을 받아 0인지 체크해야 한다. (둘 다 0이면 종료)
        h = Integer.parseInt(strs[1]);

        while (w != 0 && h != 0) {//w와 h가 0이 아닌 상황에서 무한 반복
            graph = new int[h][w];//h가 높이이기 때문에 [h][w]
            int sumCnt = 0;//섬의 개수 출력을 위한 변수

            //지도 초기화
            for (int i = 0; i < h; i++) {
                strs = br.readLine().split(" ");
                for (int j = 0; j < w; j++) {
                    graph[i][j] = Integer.parseInt(strs[j]);
                }
            }

            //bfs 수행
            /*
             graph 지도를 한 점씩 방문하여 방문시에
             bfs로 한 시도당, 방문한 모든 섬의 1의 값을 0으로 변환할 것이기 때문에
             지도에서 좌표가 0인 경우, 바다 or 이미 지워진 섬이다.
             섬의 개수만 세면 되기 때문에 그냥 graph에서 차례로 섬을 지워가며 개수 counting한다.
            */
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (graph[i][j] != 0) {
                        sumCnt++;
                        bfs(i, j);
                    }
                }
            }

            sb.append(sumCnt + "\n");

            strs = br.readLine().split(" ");
            w = Integer.parseInt(strs[0]);
            h = Integer.parseInt(strs[1]);
        }
        System.out.println(sb.toString());
    }

bfs

/*
    기본적인 너비 우선 탐색으로 모든 좌표를 탐색하여 팔방으로 연결되어있는 섬의 경우 0으로 변환해준다.
*/

    static void bfs(int x, int y) {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x, y));
        graph[x][y] = 0;
        while (!q.isEmpty()) {
            Node node = q.poll();
            //8방 돌면서 link되어있는지 체크
            for (int i = 0; i < nX.length; i++) {
                int nextX = nX[i] + node.x;
                int nextY = nY[i] + node.y;
                if(nextX < 0 || nextX >= h || nextY < 0 || nextY >= w) continue;
                if (graph[nextX][nextY] == 1) {
                    graph[nextX][nextY] = 0;
                    q.offer(new Node(nextX, nextY));
                }
            }
        }
    }