[Java] 백준 BOJ / 4963번: 섬의 개수

섬의 개수

문제

문제 설명

여러 개의 테스트 케이스가 주어지고 너비 w와 높이 h가 주어졌을 때 상하좌우, 또는 대각선으로 이어진 섬의 개수를 출력하는 문제이다.

따로 예외처리할 사항은 없고 그냥 문제조건에 맞게 DFS를 해주면 풀리는 문제였다.

일반적인 다른 그래프 문제와 다른 점이라면 기존 그래프 탐색에서는 방향이 상하좌우뿐이였다면 이번 문제는 대각선이 포함되었다는 점이다.

그래서 dx와 dy 배열을 총 8방향으로 잘 생각해서 아래와 같이 선언해주어야 한다.

static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
static int[] dy = {1, -1, 0, 1, -1, 1, -1, 0};

코드

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

public class Main_4963 {
    static int w, h;
    static int[][] arr;
    static boolean[][] visited;

    static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
    static int[] dy = {1, -1, 0, 1, -1, 1, -1, 0};

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

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

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

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

            int result = 0;

            arr = new int[h][w];
            visited = 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());
                }
            }

            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if(!visited[i][j] && arr[i][j] == 1) {
                        dfs(i, j);
                        result++;
                    }
                }
            }
            System.out.println(result);
        }

    }

    public 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 && nx < h && ny >= 0 && ny < w) {
                if (!visited[nx][ny] && arr[nx][ny] == 1) {
                    dfs(nx, ny);
                }
            }
        }
    }
}