[BOJ/백준] 4963. 섬의 개수 (JAVA)

링크

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

 

 

문제 요약

h*w 사각형 지도에 섬 또는 바다가 표시되어 있을 때 섬의 개수를 반환하기

이때 가로, 세로, 대각선으로 연결되어 있는 섬은 같은 섬이다.

 

제한

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

 

풀이

가로, 세로, 대각선으로 연결되어 있지 않은 1의 개수를 세는 문제입니다.

 

즉, 영역의 개수를 구하는 문제이므로 DFS 또는 BFS로 풀 수 있습니다.

저는 DFS로 문제를 풀었습니다.

 

1. 시작점으로부터 가로, 세로, 대각선 방향으로 탐색 가능한 모든 땅(1) 칸을 찾는다.
   1. 아직 방문하지 않은 땅(1)만 시작점이 될 수 있다.
   2. 시작점 근처의 땅(1) 칸을 발견면, 다음 기준점을 해당 칸으로 지정하여 연속적으로 탐색한다.
   3. 각 칸에 방문 표시를 남긴다.
2. 더 이상 탐색 가능한 땅(1) 칸이 없으면, 하나의 섬 영역에 대한 탐색이 완료된 것이다.
3. 다음 시작점을 기준으로 1~3 과정을 반복한다.
   1. 각 시작점마다 섬 개수 카운트를 1 증가시킨다.

 

탐색 가능한 영역의 기준은 다음 3가지 기준을 모두 만족해야 합니다.

1. 지도 범위 내부여야 한다.(지도 범위 밖이면 런타임 에러 발생 가능)
2. 값이 1이어야 한다.(=바다가 아닌 섬이어야 한다)
3. 이전에 방문한 적이 없는 영역이어야 한다.

⇒ 이 조건들을 잘 고려하여 문제를 풀어야 합니다!

 

코드

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

public class Main {
    static boolean[][] visited;
    static int[][] board;
    static int cnt;
    static int[] dirX = {1,0,-1,0,1,-1,-1,1};
    static int[] dirY = {0,1,0,-1,1,1,-1,-1};
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        while(true) {
            cnt = 0;
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());
            if (w == 0 && h == 0) return;
            visited = new boolean[h][w];
            board = new int[h][w];

            for(int i=0; i<h; i++){
                st = new StringTokenizer(br.readLine());
                for(int j=0; j<w; j++){
                    board[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            for(int i=0; i<h; i++){
                for(int j=0; j<w; j++){
                    if(!visited[i][j] && board[i][j]==1) {
                        dfs(i,j);
                        cnt++;
                    }
                }
            }
            System.out.println(cnt);
        }
    }

    static void dfs(int curx, int cury){
        visited[curx][cury] = true;
        for(int i=0; i<dirX.length; i++){
            int nx = curx+dirX[i];
            int ny = cury+dirY[i];

            if(nx<0 || ny<0 || nx>=board.length || ny>=board[0].length) continue;
            if(visited[nx][ny] || board[nx][ny]==0) continue;

            visited[nx][ny] = true;
            dfs(nx,ny);
        }
    }
}

🏷 시간 복잡도

• 첫 2중 for문: `O(h*w)`
• 두 번째 2중 for문: `O(h*w)`
  • dfs 함수가 아직 방문하지 않은 1 값 개수만큼 호출하게 되므로 `O(h*w)`
    • 1 값(땅) 개수는 최대 `h*w`
• 최종 시간 복잡도: `O(hw)`+`O(hw)` = `O(h*w)` = `O(N)`
  • `N`=`h*w`
  • N의 최댓값은 50*50=2500

 

🏷 실행 속도

Time: 144 ms, Memory: 15876 KB