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

 

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

4963번: 섬의 개수

 

 

문제 해결 프로세스 및 꿀팁

대각선도 이동이 가능하므로 길이가 8인 델타 배열을 만듭니다. (팔방탐색)

원래 DFS는 visited 배열을 만들어 검사해줍니다.

하지만 이런 문제같은 경우에는 1을 지날 때 0으로 바꾸어주면 됩니다.

map의 좌표 중 1인 곳만 탐색하기 때문에, 0으로 바꾸어준 곳은 더이상 다른 곳에서 탐색하지 않기 때문입니다.

 

한 가지 꿀팁을 드리자면!!

map의 좌표를 w+2, h+2로 설정하여 패딩을 준다면 범위 체크 조차 할 필요가 없어집니다.

꼭짓점이나 변에서 8방 탐색을 해도 사방에 패딩이 생겼기 때문에 ArrayOutOfIndex 에러가 나지 않습니다.

한 줄이라도 코드를 줄이기 위해..!!

 

정답코드는 다음과 같습니다.

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[] dr = {-1, 1, 0, 0, -1, -1, 1, 1};
    static int[] dc = {0, 0, -1, 1, -1, 1, -1, 1};

    static int w, h;
    static int[][] map;

    static int ans = 0;
    static StringBuilder sb = new StringBuilder();
    public static void findIsland (int r, int c) {
        map[r][c] = 0;

        for (int d = 0; d < 8; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (map[nr][nc] == 1) {
                map[nr][nc] = 0;
                findIsland(nr, nc);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        while (true) {
            ans = 0;
            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 + 2][w + 2];
            for (int i = 1; i <= h; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 1; j <= w; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            for (int i = 1; i <= h; i++) {
                for (int j = 1; j <= w; j++) {
                    if (map[i][j] == 1) {
                        ans++;
                        findIsland(i, j);
                    }
                }
            }
            sb.append(ans).append('\n');
        }
        System.out.println(sb);
    }
}