[BOJ4963] 섬의 개수

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

4963번: 섬의 개수

 

0️⃣

문제

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

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

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

 

입력

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

출력

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

 

1️⃣ 어떻게 문제를 풀까?

완전탐색 + 시뮬레이션 문제..? 사실 문제 유형을 잘 파악 못하겠다.. DFS카테고리에서 발견했는데, 내가 DFS로 푼것 같진 않아서..

내가 푼 로직은,

• 모든 칸을 돌면서 섬인지 아닌지 isNewIsland()를 확인한다. true일 경우 answer += 1을 해준다.
• isNewIsland() 메서스 안에서는 해당 칸이 바다인지를 확인 → Island 라면, 이미 체크가 되었는지 확인 → 그 후 해당 칸과 그 칸과 연결된 섬을 check[][]에 표시하는 mark()메서드를 호출
• mark() 메서드 안에서는 시뮬레이션 문제처럼 자신을 둘러싼 모든 칸을 확인하며 mark()를 수행!

import java.util.*;

public class Main {
    public static int[][] map;
    public static boolean[][] check;
    public static int[] dx = new int[]{0, 1, 1, 1, 0, -1, -1, -1};
    public static int[] dy = new int[]{-1, -1, 0, 1 , 1, 1, 0, -1};
    public static int w, h;
    
    public static boolean isIsland(int r, int c) {
        if(check[r][c]) return false;
        if(map[r][c] == 0) return false;
        
        mark(r, c);
        
        return true;
    }
    
    public static void mark(int r, int c) {
        check[r][c] = true;
        
        for(int i = 0; i < 8; ++i) {
            int nr = r + dy[i]; int nc = c + dx[i];
            if(check[nr][nc] || nr < 0 || nr >= h || nc < 0 || nc >= w) continue;
            if(map[nr][nc] == 1) {
                check[nr][nc] = true;
                mark(nr, nc);
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        w = sc.nextInt(); h = sc.nextInt();
        
        while(!(w == 0 && h == 0)) {
            int answer = 0;
            map = new int[h][w];
            check = new boolean[h][w];
    
            for(int r = 0; r < h; ++r)
                for(int c = 0; c < w; ++c) map[r][c] = sc.nextInt();

            for(int r = 0; r < h; ++r)
                for(int c = 0; c < w; ++c) if(isNewIsland(r, c)) answer++;
            
            System.out.println(answer);
            
            w = sc.nextInt(); h = sc.nextInt();
        }
    }
}