BOJ - 섬의 개수 (4963)

• 그래프 탐색 문제이다.
• 탐색 경로가 가로, 세로, 대각선 8방향 조건을 이용하여 처리한다.
• 연결 요소의 개수 문제에서 탐색 조건이 추가된 문제이다.
• https://developer-h.tistory.com/entry/BOJ-%EC%97%B0%EA%B2%B0-%EC%9A%94%EC%86%8C%EC%9D%98-%EA%B0%9C%EC%88%98-11724
• 입력이 다소 복잡한 문제인듯!!

BOJ - 연결 요소의 개수 (11724)

 

import java.util.Scanner;


public class Main {
    public static final Scanner scanner = new Scanner(System.in);

    public static final int SEA = 0;

    public static void main(String[] args) throws Exception {

        while (true) {
            int W = scanner.nextInt();
            int H = scanner.nextInt();

            if (isTestCaseEnd(W, H)) {
                break;
            }

            if (W == 1 && H == 1) {
                System.out.println(scanner.nextInt());
                continue;
            }

            int[][] map = new int[H + 1][W + 1];
            boolean[][] visited = new boolean[H + 1][W + 1];

            for (int i = 1; i <= H; i++) {
                for (int j = 1; j <= W; j++) {
                    map[i][j] = scanner.nextInt();
                }
            }
            dfs(map, visited);
        }
    }

    private static void dfs(int[][] map, boolean[][] visited) {
        int path = 0;
        for (int i = 1; i < map.length; i++) {
            for (int j = 1; j < map[i].length; j++) {
                if(map[i][j] != SEA && visited[i][j] == false) {
                    path += 1;
                    dfs(i, j, map, visited);
                }
            }
        }
        //경로 횟수 => 연결된 섬 경로의 수
        System.out.println(path);
    }

    private static void dfs(int r, int c, int[][] map, boolean[][] visited) {
        //탐색 종료 조건
        if (r >= map.length || r <= 0) return;
        if (c >= map[r].length || c <= 0) return;
        if (map[r][c] == SEA) return;
        if (visited[r][c] == true) return;

        visited[r][c] = true;

        //가로, 세로, 대각선
        dfs(r, c + 1, map, visited);
        dfs(r, c - 1, map, visited);
        dfs(r + 1, c, map, visited);
        dfs(r - 1, c, map, visited);
        dfs(r + 1, c + 1, map, visited);
        dfs(r - 1, c + 1, map, visited);
        dfs(r + 1, c - 1, map, visited);
        dfs(r - 1, c - 1, map, visited);
    }

    private static boolean isTestCaseEnd(int w, int h) {
        return w == 0 && h == 0;
    }
}