BOJ_S2_4963

📁 [S2_4963] 섬의 개수

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

public class Main {
    static StringTokenizer st;
    static int[][] arr;
    static int w, h;
    static boolean[][] v;
    static int[] dx = {-1, -1, -1, 0, 1, 1, 1, 0};
    static int[] dy = {-1, 0, 1, 1, 1, 0, -1, -1};

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

        while (true) {
            st = new StringTokenizer(br.readLine(), " ");

            // 너비 w, 높이 h
            w = Integer.parseInt(st.nextToken());

            h = Integer.parseInt(st.nextToken());

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

            // 지도
            arr = new int[h][w];

            // 섬인지 아닌지 check
            v = new boolean[h][w];

            // 섬의 개수
            int cnt = 0;

            // 지도 입력
            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());
                }
            }

            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (arr[i][j] == 1 && !v[i][j]) {
                        dfs(j, i);
                        cnt++;
                    }
                }
            }
            sb.append(cnt).append("\n");
        }
        System.out.println(sb);
    }

    static void dfs(int x, int y) {
        v[y][x] = true;

        int nx, ny;
        for (int z = 0; z < 8; z++) {
            nx = x + dx[z];
            ny = y + dy[z];

            if (nx < 0 || ny < 0 || nx >= w || ny >= h) {
                continue;
            } else if (arr[ny][nx] == 1 && !v[ny][nx]) {
                dfs(nx, ny);
            }
        }
    }
}

🤔 나의 생각

섬이 가로,세로,대각선 까지 연결이 될 수 있어서 8방향 탐색을 사용했다.
그리고 깊이 우선 탐색을 이용하여 연결되있는 곳들을 파악했다.
dfs()를 한번 다 실행해주면 카운팅을 해주어 총 섬의 개수를 구해주었다.
방향 탐색과 dfs()를 잘 알고 있다면 간단하게 풀렸을 문제이다.