[백준] 4963번: 섬의 개수 (Java)

1 . 문제 설명

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

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

걸어갈 수 있는 경로가 있어야 같은 섬에 있는 것이다.

지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

• 지도의 너비 w와 높이 h: 50보다 작거나 같은 양의 정수
• 지도 정보: 1은 땅, 0은 바다
• 입력의 마지막 줄에는 0이 두 개 주어진다.

 

• 시간 제한: 1초
• 메모리 제한: 128MB

 

2. 접근 방식

• 입력
  • 지도의 너비 w와 높이 h를 입력받는다.
  • h개 줄의 지도 정보를 입력받는다.
  • w와 h가 모두 0이면 프로그램을 종료한다.
• 지도의 모든 위치를 순회한다.
  • 아직 방문하지 않은 위치에서 DFS를 사용한다. → 섬 개수 + 1
• DFS
  • 방문한 경우 visited 배열로 방문 여부를 체크한다.
  • 방향 배열을 사용하여 8 방향(상하좌우, 대각선)을 탐색한다.
  • 지도 범위에 유효하고 아직 방문하지 않은 경우, DFS를 재귀 호출한다.

 

3. 최종 코드

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

public class Main {

    static int w, h; // 너비, 높이
    static int[][] map; // 지도 (1: 땅, 0: 바다)
    static boolean[][] visited; // 방문 여부 확인
    static boolean end = false;

    // 상하좌우, 대각션 탐색 배열
    static int[] dx = {-1, -1, -1, 0, 1, 1, 1, 0};
    static int[] dy = {1, 0, -1, -1, -1, 0, 1, 1};

    static void DFS(int x, int y) { // 높이, 너비
        visited[x][y] = true;

        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx>=0 && ny>=0 && nx<h && ny<w // 지도 범위가 유효하고
                    && !visited[nx][ny] && map[nx][ny] == 1) { // 아직 방문하지 않은 땅인 경우
                DFS(nx, ny);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        while (!end) {
            st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());

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

            // 지도 정보 저장
            map = new int[h][w];
            for (int i = 0; i < h; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < w; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            visited = new boolean[h][w];
            int count = 0; // 섬의 개수
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (!visited[i][j] && map[i][j] == 1) {
                        // 아직 방문하지 않고, 땅인 경우
                        DFS(i, j);
                        count++;
                    }
                }
            }
            sb.append(count + "\\n");
        }

        System.out.println(sb);
        br.close();
    }
}

시간복잡도: $O(T * w * h)$

$T$: 테스트 케이스, $w * h$: DFS

 

4. 분석 및 참고사항

BFS도 가능하다.