[백준] 4963번 - 섬의 개수 java

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

 

난이도 : S2

Tag : BFS/DFS

풀이 일자 : 2025-03-04

---

문제 탐색하기

w: 지도의 너비 (1 <= w <= 50)

h: 지도의 높이 (1 <= h <= 50)

00: 종료 

 

땅은 "1"

바다는 "0"

 

이때 같은 섬의 기준은 "가로", "세로", "대각선"으로 연결되어 있어야 합니다.

즉, 지도가 주어졌을 때 위 조건을 만족하는 서로 다른 모든 섬의 개수를 세는것이 문제의 핵심입니다.

가능한 시간복잡도

지도의 가로 세로 최대 높이가 50이므로 각 위치를 한 번씩은 무조건 탐색해야 합니다. 

그 위치에 존재하는게 섬인지 바다인지 알아야 하니까요.

 

즉, 모든 위치를 방문해야 하므로 기본적으로 O(w × h)의 시간이 걸립니다.
그리고 섬을 찾으면 DFS를 통해 연결된 모든 칸을 방문해야 하므로, 추가적인 탐색이 발생할 수 있습니다.

알고리즘 선택

DFS를 선택해 보겠습니다.

지도의 최대 크기가 50 × 50으로 2500개의 칸이 주어집니다.

DFS의 시간 복잡도는 O(w × h)로, 한번 방문한 곳은 다시 방문하지 않습니다.

그러므로 최악의 경우에도 2500번의 탐색이면 충분하기에 문제 해결에 적합합니다.

 

---

코드 설계하기

1. while문을 이용하여 여러 개의 테스트 케이스를 받을 수 있도록 합니다.
2. 지도의 w, h를 입력받고, 해당 크기의 지도를 생성합니다. 또한 같은 크기에 방문 확인 배열도 생성합니다.
3. dfs를 사용하여 서로 다른 섬의 개수를 탐색합니다.
   • 이때, 상, 하, 좌, 우, 대각선 총 8방향을 탐색해야 합니다.
4. w와 h가 각각 0일 경우 while문을 종료합니다.

시도 회차 별 수정사항

1. dfs(시작위치 행, 시작위치 열, 지도 높이, 지도 넓이)를 인자로 넘겨야 하는데  dfs(시작위치 행, 시작위치 열, 지도 넓이, 지도 높이) 로 바꿔 입력받아 범위 오류가 났다. 그래서 인자를 서로 바꿔줬다.

---

정답 코드

import java.util.*;

class Main {
    public static int map[][];
    public static boolean visited[][];
    public static int[] dx = {0,0,1,-1,1,1,-1,-1};
    public static int[] dy = {1,-1,0,0,1,-1,-1,1};
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(true){
            int w = sc.nextInt();
            int h = sc.nextInt();
    
            if(h == 0 && w == 0) break;
            map = new int[h][w]; 
            visited = new boolean[h][w];
            
            for(int i=0; i<h; i++){
                for(int j=0; j<w; j++){
                    map[i][j] = sc.nextInt();
                }
            }
            
            int cnt = 0;
            for(int i=0; i<h; i++){
                for(int j=0; j<w; j++){
                    if(visited[i][j] || map[i][j] == 0) continue;
                    dfs(i,j,h,w);
                    cnt++;
                }
            }
            System.out.println(cnt);
        }
        sc.close();
    }
    public static void dfs(int y, int x, int h, int w){
        visited[y][x] = true;
        
        for(int i=0; i<8; i++){
            int ny = y+dy[i];
            int nx = x+dx[i];
            
            if(ny < 0 || nx < 0 || ny >= h || nx >= w) continue;
            if(visited[ny][nx] || map[ny][nx] == 0) continue;
            
            dfs(ny, nx, h, w);
        }
    }
}