[백준 4963 / Silver2] 섬의 개수 - Java(자바)

❓문제 설명

작성자 : 김민규
문제 링크 : https://www.acmicpc.net/problem/4963

• 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.
  
  한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.
  두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

❗입출력

[입력]

• 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.
• 둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.
• 입력의 마지막 줄에는 0이 두 개 주어진다.
  [출력]
  각 테스트 케이스에 대해서, 섬의 개수를 출력한다.
  [예시]
  

🎁 문제 풀이

• 지도의 크기인 w와 h를 입력받습니다.
• w와 h가 0인 경우 입력이 종료됩니다.
• 지도인 map과 섬들의 연결여부를 확인할 checked를 선언합니다.
• 지도의 섬과 바다의 정보를 map에 저장합니다.
• map에서 섬인 곳이면서 아직 섬들의 연결여부를 확인하지 않은 곳이 있으면 dfs를 통해서 주변에 연결된 섬이 있는지 확인하고 cnt를 증가시킵니다.
• dfs를 통해서 현재 좌표의 상하좌우와 대각선 방향들의 섬의 연결여부를 확인합니다.
• 모든 x,y좌표에 대해서 탐색을 완료하고 cnt를 출력하여 섬의 갯수를 출력합니다.

🖥️ 코드

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

public class Main {
    static int[][] map;
    static boolean[][] checked;
    static int w;
    static int h;
    static int dx[] = {0, 0, -1, 1, -1, 1, -1, 1};
    static int dy[] = {-1, 1, 0, 0, 1, 1, -1, -1};

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        while (true) {
            h = sc.nextInt();
            w = sc.nextInt();
            sc.nextLine();

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

            map = new int[w][h];
            checked = new boolean[w][h];

            for (int i = 0; i < w; i++) {
                String temp = sc.nextLine();
                String[] nums = temp.split(" ");
                for (int j = 0; j < h; j++) {
                    map[i][j] = Integer.parseInt(nums[j]);
                }
            }
            int cnt = 0;

            for (int i = 0; i < w; i++) {
                for (int j = 0; j < h; j++) {
                    if (map[i][j] == 1 && !checked[i][j]) {
                        dfs(i, j);
                        cnt++;
                    }
                }
            }
            System.out.println(cnt);
        }
    }

    private static void dfs(int x, int y) {
        checked[x][y] = true;
        for (int i = 0; i < 8; i++) {
            int nowX = x + dx[i];
            int nowY = y + dy[i];
            if (nowX >= 0 && nowX < w && nowY >= 0 && nowY < h) {
                if (map[nowX][nowY] == 1 && !checked[nowX][nowY]) {
                    dfs(nowX, nowY);
                }
            }
        }
    }
}