[백준 알고리즘] 4963번 섬의 개수(Java) 문제 풀이

문제

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

4963번: 섬의 개수

문제에 대한 이해

주어진 2차원 배열에서 1이라는 해당 영역을 탐색하는 DFS 문제이다.

문제를 보고 DFS의 간단한 문제라고 생각했다.

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램 = DFS나 BFS로 섬의 갯수를 찾아달라.

어떻게 풀 것인가?

문제의 조건 

w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

를 확인한 이후에는 DFS로 풀기어야겠다고 생각했다. 코드를 본다면 DFS의 문제에 대한 패턴을 확인할 수 있다.

arr <- 지도의 영역을 보여주는 2차원 배열

visit <- 방문한 영역 체크하는 2차원 배열

dirX, dirY <- 상, 하, 좌, 우, 대각선 상좌, 상우, 하좌, 하우를 체크하기 위한 좌표 배열

시간복잡도

시간복잡도의 경우 섬의개수마다 달라지긴하지만 우선은 O(N)이라고 생각한다.

공간복잡도

공간복잡도의 경우는 2차원 배열의 크기가 들어가기 때문에 O(N^2)이다.

풀면서 놓쳤던점

처음에 DFS,BFS에 익숙하지 않아서 애를 먹었던 것 같다. 익숙해질 수 있도록 최대한 많은 문제에 접근을 해봐야할 것 같다.

이 문제를 통해 얻어갈 것

인접행렬을 이용한 DFS 활용.

내 코드 

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

public class Main {
    static int[][] arr;
    static boolean[][] visit;
    static int[] dirX = {0, 0, -1, 1, -1, 1, -1, 1}; // 상 하 좌 우 대각선 상좌, 상우, 하좌, 하우
    static int[] dirY = {-1, 1, 0, 0, 1, 1, -1, -1}; // 상 하 좌 우 대각선 상좌, 상우, 하좌, 하우

    static int w, h, nowX, nowY;

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

        String str = " ";
        while (!(str = br.readLine()).equals("0 0")) {
            st = new StringTokenizer(str);


            w = Integer.parseInt(st.nextToken()); // 너비
            h = Integer.parseInt(st.nextToken()); // 높이
            arr = new int[h][w];
            visit = new boolean[h][w];

            for (int i = 0; i < h; i++) {
                st = new StringTokenizer(br.readLine());

                for (int j = 0; j < w; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());

                }
            }

            int island_count = 0;
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {

                    if (!visit[i][j] && arr[i][j] == 1) {
                        island_count++;
                        DFS(i, j);
                    }
                }

            }

            sb.append(island_count).append('\n');
        }

        System.out.println(sb);
    }

    static void DFS(int x, int y) {
        visit[x][y] = true;

        for (int i = 0; i < 8; i++) {
            nowX = dirX[i] + x;
            nowY = dirY[i] + y;

            if (range_check() && !visit[nowX][nowY] && arr[nowX][nowY] == 1) {
                DFS(nowX, nowY);
            }
        }

    } 

    static boolean range_check() {
        return (nowX >= 0 && nowY >= 0 && nowX < h && nowY < w);
    } // End of range_check

}