DFS - 백준4963 섬의 개수

BFS로 풀 수 있는 문제를 DFS로도 풀 수 있는 경우가 있다.
따라서 다음 문제를 BFS로도 풀어보고, DFS로도 풀어보았다.
백준4963 섬의 개수 : https://www.acmicpc.net/problem/4963

아래 풀이를 보면, DFS가 좀 더 직관적이다.
왜냐하면 칸에 방문하자마자, 방문했다고 표시하고 주변 탐색대상 중 하나를 골라 바로 또 들어간다. 이를 반복하는데, 마지막에 주변에 더 이상 갈 곳이 없으면 return해준다.
이러면 DFS탐색이 끝난다.

BFS의 경우에는 방문한 후, 주변 탐색대상을 먼저 Queue에 넣어둔다. 그리고 그 Queue에 들어가있는 대상들에 대해 차례로 들어간다. 이를 반복하는데, 마지막에 Queue에 더 이상 남은 게 없으면 while문이 끝난다.

위 두 로직을 비교해보면 확실히, 논리적으로 DFS가 더 이해하기 쉽고 BFS는 이게 뭐하는 짓인지 싶은 생각이 든다.

나의 경우에는 지금까지 BFS문제만 풀어보고, DFS로는 처음 접근해봐서 DFS가 아직 익숙하지 않다. 하지만 위와 같이 생각한다면 좀 더 받아들이기 쉬울 것 같다. 그리고 아무래도 재귀함수를 사용하다보니, static 변수를 활용하는 부분에서 백트래킹과 유사하다는 느낌도 든다.

TIP
BFS와 DFS를 선택하는 차이는 다음과 같다. 끝까지 탐색한 후에 다시 돌아와서 무언가 할 일이 있다면 DFS로 재귀를 이용해 푼다.

---

아래는 각 알고리즘으로 풀어본 코드이다.

BFS

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //문제
        //섬의 갯수 살리기
        //입력
        //여러개의 테스트 케이스
        //너비 w, 높이 h
        //둘째줄 이하 : 지도 정보
        //땅 : 1, 바다 : 0
        //입력 마지막 줄 : 0 0
        //풀이
        //w와 h가 0 0 으로(마지막입력으로) 들어오면, while(true)를 break
        StringTokenizer st;
        while(true){
            //w, h 입력
            st = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            //마지막입력시 break
            if(x+y == 0){
                break;
            }
            //지도 정보 입력받기
            int[][] jido = new int[x][y];
            for(int i = 0; i < x; i++){
                st = new StringTokenizer(br.readLine());
                for(int j = 0; j < y; j++){
                    jido[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            //알고리즘 실행(섬의 갯수 리턴)
            int ans = bfs(x, y, jido);
            //int ans = dfs(w, h, jido);
            System.out.println(ans);
        }
    }
    static int bfs(int x, int y, int[][] jido){
        int ans = 0;
        //12시부터 시계방향으로 검사
        int[] bx = {0, 1, 1, 1, 0, -1, -1, -1};
        int[] by = {-1, -1, 0, 1, 1, 1, 0, -1};
        //지도탐색 시작
        for(int i = 0; i < x; i++){
            for(int j = 0; j < y; j++){
                //땅이 없으면 continue
                if(jido[i][j] != 1){
                    continue;
                }
                Queue<Point> queue = new LinkedList<>();
                //첫번째칸 방문
                queue.add(new Point(i, j));
                jido[i][j] = 0;
                //bfs순회 시작
                while(!queue.isEmpty()){
                    Point now = queue.remove();
                    for(int k = 0; k < 8; k++){
                        int nx = now.x + bx[k];
                        int ny = now.y + by[k];
                        //ArrayOfBoundary Exception 검사
                        if(nx < 0 || nx >= x || ny < 0 || ny >= y){
                            continue;
                        }
                        //땅이 있는지(또는 방문했는지) 검사
                        if(jido[nx][ny] != 1){
                            continue;
                        }
                        queue.add(new Point(nx, ny));
                        jido[nx][ny] = 0;
                    }
                }
                ans++;
            }
        }
        return ans;
    }
    static class Point{
        int x;
        int y;
        Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
}

DFS

import java.util.*;
import java.io.*;
public class Main{
    static int x;
    static int y;
    static int[][] jido;
    static int[] bx = {0, 1, 1, 1, 0, -1, -1, -1};
    static int[] by = {-1, -1, 0, 1, 1, 1, 0, -1};
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //문제
        //섬의 갯수 살리기
        //입력
        //여러개의 테스트 케이스
        //너비 w, 높이 h
        //둘째줄 이하 : 지도 정보
        //땅 : 1, 바다 : 0
        //입력 마지막 줄 : 0 0
        //풀이
        //w와 h가 0 0 으로(마지막입력으로) 들어오면, while(true)를 break
        StringTokenizer st;
        while(true){
            //w, h 입력
            st = new StringTokenizer(br.readLine());
            y = Integer.parseInt(st.nextToken());
            x = Integer.parseInt(st.nextToken());
            //마지막입력시 break
            if(x+y == 0){
                break;
            }
            //지도 정보 입력받기
            jido = new int[x][y];
            for(int i = 0; i < x; i++){
                st = new StringTokenizer(br.readLine());
                for(int j = 0; j < y; j++){
                    jido[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            //알고리즘 실행(섬의 갯수 리턴)
            //int ans = bfs(w, h, jido);
            int ans = 0;
            for(int i = 0; i < x; i++){
                for(int j = 0; j < y; j++){
                    //땅이 아니면 continue;
                    if(jido[i][j] != 1){
                        continue;
                    }
                    dfs(i, j);
                    //섬의 갯수++
                    ans++;
                }
            }
            System.out.println(ans);
        }
    }
    static void dfs(int nowX, int nowY){
        //마지막 depth에서 주변에 땅이 없으면 return
        if(jido[nowX][nowY] != 1){
            return;
        }
        //현재 방문한 땅 표시
        jido[nowX][nowY] = 0;
        for(int i = 0; i < 8; i++){
            int nx = nowX + bx[i];
            int ny = nowY + by[i];
            if(nx < 0 || nx >= x || ny < 0 || ny >= y){
                continue;
            }
            if(jido[nx][ny] != 1){
                continue;
            }
            //주변 땅(여덟 방향)중 하나에 대해서 방문
            dfs(nx, ny);
        }
    }
    static class Point{
        int x;
        int y;
        Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
}