[DFS] 백준 - 4963번: 섬의 개수 Java 풀이

[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!]

 

 

문제는 맵 안에 섬이 있는데 사람은 대각선으로 된 섬을 건너갈 수 있고 이렇게 건너갈 수 있는 섬들이 총 몇 개인가를 세는 것이다.

위 문제는 X, Y 좌표값을 이용하여 문제를 풀어야 한다.

문제를 보면 대각선의 섬까지 걸어갈 수 있으므로
나는 static으로 아래와 같이 설정했다.

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

그리고 DFS를 사용하여 0, 0부터 주변에 섬들이 있는지 X, Y 축을 이용하여 검색하고 있으면 또 거기서 연결되는 섬이 있는지 체크를 하였다.
그 후, 없을 경우 다음 노드 중 방문하지 않았고 섬이 있다면 방문하여 또 위와 같은 작업을 반복하였다.

코드

import java.util.Scanner;

public class Main {
    static int[][] map;
    static boolean[][] check;
    static int w;
    static int h;
    static int dx[] = {0, 0, -1, 1, -1, 1, -1, 1};
    static int dy[] = {-1, 1, 0, 0, 1, 1, -1, -1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while (true) {
            h = sc.nextInt();
            w = sc.nextInt();
            sc.nextLine();

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

            map = new int[w][h];
            check = new boolean[w][h];

            for (int i = 0; i < w; i++) {
                String tempStr = sc.nextLine();
                String[] nums = tempStr.split(" ");

                for (int j = 0; j < nums.length; j++) {
                    map[i][j] = Integer.parseInt(nums[j]);
                }
            }

            int count = 0;

            for (int i = 0; i < w; i++) {
                for (int j = 0; j < h; j++) {
                    if (map[i][j] == 1 && !check[i][j]) {
                        dfs(i, j);
                        count++;
                    }
                }
            }

            System.out.println(count);
        }
    }

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

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

            if (nowX >= 0 && nowY >= 0 && nowX < w && nowY < h) {
                if (map[nowX][nowY] == 1 && !check[nowX][nowY]) {
                    dfs(nowX, nowY);
                }
            }
        }
    }
}