BOJ 1103) 게임

 

 예전에 풀었던, dp 메모이제이션을 이용하는 bfs/dfs문제인 ACM craft(https://eckrin.tistory.com/entry/BOJ-1005-ACM-Craft?category=985109)들과 유사한 문제다. 이런 유형의 문제를 한두번 푸는것이 아닌데도 계속 헷갈리는 이유는, dp를 사용했다고 해서 메모이제이션을 사용하는 것이 아니라는 사실을 자꾸 망각해서 그렇다.

 

 뭔 소리나면,

Queue<Location> queue = new LinkedList<>();
queue.add(new Location(0,0));
while(!queue.isEmpty()) {
    Location removeLoc = queue.remove();
    int x = removeLoc.x;
    int y = removeLoc.y;
    int value = arr[x][y];
    if(depth[x][y]>2500) {
        System.out.println("-1");
        return;
    }
    if(x-value>=0 && arr[x-value][y]!=0) {
        depth[x-value][y] = depth[x][y]+1;
        queue.add(new Location(x-value, y));
    }
    ...

큐를 사용한 평범한 bfs 코드이다. 좌표의 최대 접근 길이(depth)를 계산할 때,

if(x-value>=0 && arr[x-value][y]!=0) {
    depth[x-value][y] = depth[x][y]+1;
    queue.add(new Location(x-value, y));
}

위 코드는 이전에 계산해놓은 depth값을 이용해서 현재 탐색하고자 하는 depth를 구한다. 사실 이 코드도 이전에 구한 값을 이용해서 불필요한 중복 계산을 줄이므로 dp가 맞긴 하다. 그런데 여기서 중요한 것은 bfs나 dfs로 탐색할 때, dp를 이용해서 불필요한, 추가적인 탐색 없이 dp값을 사용해서 branch의 탐색을 중단해야 한다는 것이다.

 

다시 말해서, "x-value>=0이고(=ArrayIndexOutOfBounds 예외가 발생하지 않고), arr[x-value][y]!=0이면(=구멍에 떨어지지 않으면)"이라는 두가지 당연한 종료조건에 대해서만 검사하고 있다. 이러한 경우, 최대값을 구해야 하는 탐색 문제이기 때문에, 이미 구해진 값보다 작은 depth값을 갖는 탐색은 더이상 불필요한 탐색임에도 탐색을 지속하게 된다. 즉, 이미 방문한 지점이라면 dp를 이용해서 바로 최대 이동 횟수를 반환하도록 로직을 수정해야 한다는 것이다.

if(x-value>=0 && arr[x-value][y]!=0) {
    //이미 방문한 좌표를 다시 방문할 때, 좌표의 최대 dp값이 현재 나의 dp값보다 작을 경우에만 탐색
    if(depth[x-value][y]<depth[x][y]+1) {  
        depth[x-value][y] = depth[x][y]+1;
        queue.add(new Location(x-value, y));
    }
}

그렇게 하기 위해서는 이미 방문한 좌표를 다시 방문하는 상황에 좌표에 이미 존재하는 depth값이 현재 구해나가고 있는 depth값보다 크다면, 현재 탐색하고 있는 탐색의 branch는 더이상 promising하지 않다는 것을 말한다.

 

 

최소 depth를 구하는 문제와 맥락만 다를 뿐, 완전히 동일한 로직이다. 탐색에 걸리는 최소값을 구하는 문제의 경우, bfs로 처음 접근이 이루어졌을 경우 그 때의 depth가 최소값이 되며, 더 이상 탐색이 의미가 없다. 이 문제 또한, 이미 접근이 이루어진 경우 현재 탐색 경로의 depth가 구하는 좌표의 depth보다 작다면 더 이상 탐색이 의미없게 되는 것이다.

 

 

시간복잡도 차원에서 생각해보자. 그래프에 정점이 N*M개가 있는데, dfs탐색 한번에 동/서/남/북 4방향 최대 4가지 경우로 분기하므로 대략 O(4^[N*M])의 시간복잡도를 가진다. (정확하지는 않지만, 지수시간 시간복잡도를 갖는다.)

메모이제이션을 사용하면, N*M개의 정점을 모두 탐색한 이후에는 메모이제이션을 통한 접근 (탐색의 dp값이 갱신될 경우에만 접근)이 이루어진다.

>> 시간복잡도는 어떻게 계산해야될지 모르겠다. 반복된 접근이 얼마나 될 것인가를 어떻게 계산하지

 

 

 

import java.util.*;
import java.io.*;

public class Main {

    static int[][] arr;
    static int[][] depth;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line_1 = br.readLine().split(" ");
        int N = Integer.parseInt(line_1[0]);
        int M = Integer.parseInt(line_1[1]);
        arr = new int[N][M];
        depth = new int[N][M];
        int max=0;

        //배열에 입력받기
        for(int i=0; i<N; i++) {
            String line = br.readLine();
            for(int j=0; j<M; j++) {
                char number = line.charAt(j);
                if(number=='H') {
                    arr[i][j] = 0; //구멍일경우 0
                    continue;
                }
                arr[i][j] = number-'0';
            }
        }

        //핵심1: 무한대로 움직이는 경우를 어떻게 잡아내야하나.
        //핵심2: 큰 값을 구하는거니깐 옛날에 풀었던 문제들처럼 dp가 0인 경우에만 쓰도록 할 수는 없다.
        //대신, 작은 값으로 접근하는 경우의 수는 필요 없으므로 접근을 막으면 된다.
        Queue<Location> queue = new LinkedList<>();
        queue.add(new Location(0,0));
        while(!queue.isEmpty()) {
            Location removeLoc = queue.remove();
            int x = removeLoc.x;
            int y = removeLoc.y;
            int value = arr[x][y];
            if(depth[x][y]>2500) {
                System.out.println("-1");
                return;
            }
            if(x-value>=0 && arr[x-value][y]!=0) {
                if(depth[x-value][y]<depth[x][y]+1) { //이미 방문한 좌표를 다시 방문할 때, 좌표의 최대 dp값이 현재 나의 dp값보다 작을 경우에만 탐색
                    depth[x-value][y] = depth[x][y]+1;
                    queue.add(new Location(x-value, y));
                }
            }
            if(x+value<N && arr[x+value][y]!=0) {
                if(depth[x+value][y]<depth[x][y]+1) {
                    depth[x+value][y] = depth[x][y]+1;
                    queue.add(new Location(x+value, y));
                }
            }
            if(y-value>=0 && arr[x][y-value]!=0) {
                if(depth[x][y-value]<depth[x][y]+1) {
                    depth[x][y-value] = depth[x][y]+1;
                    queue.add(new Location(x, y-value));
                }
            }
            if(y+value<M && arr[x][y+value]!=0) {
                if(depth[x][y+value]<depth[x][y]+1) {
                    depth[x][y+value] = depth[x][y]+1;
                    queue.add(new Location(x, y+value));
                }
            }
        }

        for(int i=0; i<N; i++) {
            for (int j = 0; j < M; j++) {
                if(max<depth[i][j])
                    max = depth[i][j];
//                System.out.print(depth[i][j]);
            }
//            System.out.println();
        }

        System.out.println(max+1);
    }
}

class Location {
    int x;
    int y;

    public Location(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

 

최소/최대 시간/거리/경우의수 bfs/dfs 모두 원리는 같다. 한번 탐색이 이루어지면 더 이상 다시 탐색하지 않도록 하는것이 중요하다.