[BOJ - JAVA] 1743 - 음식물 피하기(DFS)

# 주소

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

1743번: 음식물 피하기

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
class Main{
    static int n, m, k;
    static int[][] arr;
    static boolean[][] visit;
    static int answer = 0;
    static int sum = 1;
    static int[][] dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        k = scan.nextInt();
        arr = new int[n][m];
        visit = new boolean[n][m];
        for(int i = 0; i < k; i++){
            int x = scan.nextInt() - 1;
            int y = scan.nextInt() - 1;
            arr[x][y] = 1;
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(!visit[i][j]){
                    if(arr[i][j] == 1){
                        visit[i][j] = true;
                        sum = 1;
                        dfs(i, j);
                    }
                }
            }
        }
        System.out.println(answer);
    }
    static void dfs(int x, int y){
        answer = Math.max(sum, answer);
        for(int i = 0; i < 4; i++){
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            if(nx < 0 || ny < 0 || nx >= n || ny >= m)
                continue;
            if(visit[nx][ny])
                continue;
            if(arr[nx][ny] == 1){
                visit[nx][ny] = true;
                sum = sum + 1;
                dfs(nx, ny);
            }
        }
    }
}

초 간단한 DFS 문제였습니다.

DFS 문제를 안푼지 오래되어서 감을 좀 잃었습니다.

그래프 탐색 문제에 있어서 주로 BFS문제 위주로 풀다보니 DFS풀이법도 같이 챙기는게 좋아서 풀어보았습니다.

static int n, m, k;
static int[][] arr;
static boolean[][] visit;
static int answer = 0;
static int sum = 1;
static int[][] dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

정적 변수는 다음과 같이 선언했습니다.

어라 블로거님 BFS와 DFS가 차이가 없는 것 아닌가요?

visit배열도 선언하고 4가지 방향 설정도 해주면 둘의 차이가 무엇인가요? 이렇게 말씀하실 수 있습니다.

저도 100%안다고 호언장담하진 못하지만 말씀드릴 수 있는건, BFS와 DFS의 차이는 탐색 방법에 있습니다.

BFS의 경우 탐색하고자 하는 새로운 인덱스에 대해 그 주변을 탐색할 수 있는 넓이 우선 탐색기법입니다.

따라서 탐색이 가능한 것들은 모두 QUEUE라는 자료구조를 이용하여 인덱스를 담을 수 있는 것입니다.

DFS의 경우엔 한 번 탐색 가능한 경우 끝까지 파고들게 됩니다.

명칭부터 깊이 우선 탐색이기 때문에 하나를 파더라도 끝까지 판다고 이해하면 되겠습니다.

이 문제에서도 마찬가지로 탐색이 가능한 인덱스들은 모두 한 방향에 대해 나아갈 것입니다.

문제 예제에 나와 있는 것들은 표본이 작지만 만약 

1 0 0 0 

1 0 0 1

1 1 0 0

1 0 0 1 이렇게 입력받는다면 옆으로 1이 뻗어가지않고 밑으로 우선적으로 뻗어가게 할 수 있다는 것입니다.

지금은 제가 static 에서 dir 방향을 4가지를 아무렇게나 넣었지만 정석대로 하려면 {1,0}이 제일 먼저 와야 시간 낭비를 덜하겠지요.

그래야 for문에서 돌면서 굳이 탐색 안해도 되는 {-1,0} 방향을 거를 수 있는 것입니다.

어찌됐든 입력문을 살펴봅시다.

Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
k = scan.nextInt();
arr = new int[n][m];
visit = new boolean[n][m];
for(int i = 0; i < k; i++){
    int x = scan.nextInt() - 1;
    int y = scan.nextInt() - 1;
    arr[x][y] = 1;
}

저는 음식물 쓰레기가 있는 지점들은 모두 1로 선언하였습니다.

arr와 visit은 n x m크기로 지정합니다.

for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
        if(!visit[i][j]){
            if(arr[i][j] == 1){
                visit[i][j] = true;
                sum = 1;
                dfs(i, j);
            }
        }
    }
}

2중 for문을 이용하여 visit이 false이고 arr가 1인 곳들을 탐색할 것입니다.

만약 하나의 덩어리가 탐색이 완료된다면 인접해있는 모든 지점들은 visit이 true가 되기 때문에 재방문할 필요가 없게되므로 arr가 1인지점보다 visit처리를 먼저 해주었습니다.

sum은 항상 1로 초기화할텐데 왜그런지 살펴보겠습니다.

static void dfs(int x, int y){
    answer = Math.max(sum, answer);
    for(int i = 0; i < 4; i++){
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        if(nx < 0 || ny < 0 || nx >= n || ny >= m)
            continue;
        if(visit[nx][ny])
            continue;
        if(arr[nx][ny] == 1){
            visit[nx][ny] = true;
            sum = sum + 1;
            dfs(nx, ny);
        }
    }
}

dfs함수의 내부입니다. 초간단하죠?

answer는 sum과 비교하여 최댓값을 산출합니다.

그리고 4가지 방향에 대해 새로운 인덱스를 지정할텐데요.

visit이 true이거나 (방문했거나) nx와 ny가 범위를 벗어나면 continue합니다.

여기까지는 BFS와 대동소이합니다.

이후 부터가 조금씩 다른데, arr가 1인 지점에 대해 visit을 true한 후 queue에 담는 것이 아닌 dfs를 재귀로 사용합니다.

그래서 새로 갱신된 dfs에 대해 다시 answer의 최댓값을 산출하고 또 4가지 방향을 찾아서 나아가는 것이지요.

그렇기 때문에 이런 DFS 문제 종류는 dir설정을 다르게 하면 시간 복잡도가 완전히 바뀔 수 있습니다.

이 탐색을 모두 마치면 answer를 출력하시면 정답이 되겠습니다.

 

싸피를 저번주에 면접 보고 왔는데 후기는 음.. 발표나면 말씀드리겠습니다.

같이 면접 보신 분들 고생하셨고 면접관님도 고생하셨습니다. 감사합니다.