dfs문제

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

4963번: 섬의 개수

package DFS_BFS;

import java.util.Scanner;

public class 섬의개수_4963 {
    static int w, h; // 지도의 너비와 높이
    static int[][] map; // 지도를 나타내는 인접 행렬
    static boolean[][] visited; // 방문 여부를 나타내는 배열
    static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1}; // y 좌표 이동
    static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1}; // x 좌표 이동
    //대각위왼,왼,대각아래왼,위,아래,대각위오른,오른,대각아래오른

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            w = sc.nextInt(); // 지도의 너비 입력
            h = sc.nextInt(); // 지도의 높이 입력
            if (w == 0 && h == 0) {
                break; // 너비와 높이가 0인 경우 종료
            }

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

            // 지도 입력 받기
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    map[i][j] = sc.nextInt();
                }
            }

            int count = 0; // 섬의 개수를 저장할 변수
            // 전체 지도를 순회하면서 섬을 찾음
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (map[i][j] == 1 && !visited[i][j]) {
                        dfs(i, j); // 섬을 찾으면 DFS 탐색 실행
                        count++; // 섬의 개수 증가
                    }
                }
            }
            System.out.println(count); // 섬의 개수 출력
        }
    }

    // DFS 탐색 메소드
    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 && ny >= 0 && nx < h && ny < w) {
                // 이동한 위치가 섬이면서 아직 방문하지 않았다면
                if (map[nx][ny] == 1 && !visited[nx][ny]) {
                    dfs(nx, ny); // 이동한 위치에서 다시 DFS 탐색 실행
                }
            }
        }
    }
}

첫 dfs문제라 dfs에 대해 이해는 했지만 어떻게 대입해야될지 몰랐다. dfs는 완전탐색 중 백트래킹의 방법 중 하나로 말 그대로 다 돌아보며 확인하는 것이다. 위 같은 문제는 0,0부터 인접 행렬을 사용하여 8방 탐색을 하며 만약 섬이 있다면 그 섬으로 이동하여 다시 8방 탐색을 하며 dfs를 통한 깊이 우선 탐색을 하는 문제이다. 그래서 8방 탐색을 하며 완전 탐색을 하고 더이상 섬이 없다면 이제 다음 인덱스를 가며 또 8방 탐색을 하며 dfs탐색을 하는 문제이다. 어떻게 푸는지 첫 dfs문제라 어려웠지만 그래도 감은 어느정도 잡힌 것 같다. 다음에는 bfs로도 풀어봐야겠다.

결론 : 8방 탐색을 하는 방법/8방 탐색을 하며 dfs를 통한 완전 탐색 백트래킹.