[백준 20152번 / java] Game Addiction

문제

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

1. pc방으로 상하좌우 이동, 한 번에 1칸 이동
2. 최단경로로 움직임
3. y>x인 곳은 침수됨
4. 침수된 곳을 피해서 pc방까지 갈 수 있는 경로의 개수
5. pc방 좌표 == 집 좌표 -> 경로 1가지

 

입력:
(H, H) 집 좌표  (N, N) pc방 좌표

풀이1

bfs, dfs - 시간초과

 

처음에는 방문 가능한 곳의 좌표를 리스트에 넣어서 리스트의 조합으로 풀려고 했다.

그러나 이 방법은 최악의 경우 30*30행렬에서 좌표의 모든 조합을 구해야 하므로 연산 횟수가 1억이 넘는다.

 

다음으로 행렬을 완전탐색하는 경우를 생각해보았다.

완전탐색은 일반적으로 O(2^N) O(N!)의 시간복잡도를 가지고 있다. 

이 경우도 연산 횟수가 1억이 넘는다.

 

그러나 bfs, dfs를 사용하였고, 역시나 시간초과가 발생했다.

---

 

경로의 개수만 구하면 되므로, 시작점과 끝점을 (N,N) (H,H) 중 뭘로 하든 상관 없다.

1. |N-H|*|N-H|크기의 행렬을 만듦
2. (x>y)인 경우 각 좌표에 현재까지 최단거리를 저장 -> bfs:한 번만 탐색
3. '1~도착지점에 저장된 거리'까지 차례로 1씩 증가하는 경로가 몇 개 있는지 세기 -> dfs

 

테스트 케이스는 맞았지만 시간 초과가 발생하였다.

코드1

import java.io.*;
import java.util.*;
public class boj_20152 {
    static int N, H;
    static int[][] board;
    static boolean[][] check;
    static int ans;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        H = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        int size = Math.abs(N-H)+1;
        board = new int[size][size];
        check = new boolean[size][size];
        bfs(0, 0); //현재까지 최단거리 저장
        dfs(0, 0, 0); //차례로 1씩 증가하는 경로의 개수 탐색
        bw.write(ans+" ");
        bw.close();
    }
    static void bfs(int x, int y){
        Queue<Point> q = new LinkedList<>();
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
        q.offer(new Point(x, y));
        check[x][y] = true;
        while(!q.isEmpty()){
            Point p = q.poll();
            for(int i=0; i<4; i++){
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if(nx<0 || nx>=board.length || ny<0 || ny>=board.length)
                    continue;
                if(check[nx][ny] || ny > nx)
                    continue;
                board[nx][ny] = board[p.x][p.y] + 1;
                q.offer(new Point(nx, ny));
                check[nx][ny] = true;
            }
        }
    }
    static void dfs(int num, int x, int y){
        if(num == board[board.length-1][board.length-1]){
            ans++;
            return;
        }
        //오른쪽, 아래만 탐색 (0, 1) (1, 0)
        //num과 같은 숫자가 있다면 재귀, 그 좌표와 num+1을 인자로 넘겨줌
        num += 1;
        if(y+1<0 || y+1>=board.length)
            return;
        if(board[x][y+1] == num)
            dfs(num, x, y+1);
        if(x+1<0 || x+1>=board.length)
            return;
        if(board[x+1][y] == num)
            dfs(num, x+1, y);
    }
}
class Point{
    int x, y;
    public Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}

풀이2

dp

1. 각 좌표에 도달 가능한 경우의 수 저장하기

2. pc방 좌표 == 집 좌표 -> 경로 1가지 이므로 board[0][0] = 1

3. 0열의 모든 좌표는 도달 가능한 경우의 수가 1가지 뿐이므로 모두 1로 채운다.

4. 최단거리로 진행하므로 현재 좌표에서 오른쪽, 아래 두 가지 방향으로만 간다.

5. 따라서 현재 좌표에 도달 가능한 경우의 수는 왼쪽, 위에서 온 경우 뿐이므로 두 위치에 있는 수의 합이 된다.

-> board[x][y] = board[x-1][y] + board[x][y-1]

6. 주의할 점은 열>행인 좌표는 지나갈 수 없으므로, 0의 값이 들어가있어야 한다. 

-> board 선언 시 모두 0으로 초기화되어있어서 따로 넣어주지 않았다.

-> 열>행인 경우를 피해서 값을 저장하기 위해 이중 for문의 두 번째 루프에 조건을 주었다.

7. N, H값이 커지면 경우의 수가 4byte(-2^31~2^31)보다 커지므로 long타입을 사용해야 한다.

코드2

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

public class Main {
    static int N, H;
    static long[][] board;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        H = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        int size = Math.abs(N-H)+1;
        board = new long[size][size];
        board[0][0] = 1;
        for(int i=1; i<size; i++){
            board[i][0] = 1;
            for(int j=1; j<i+1; j++){
                board[i][j] = board[i-1][j] + board[i][j-1];
            }
        }
        bw.write(board[size-1][size-1] + " ");
        bw.close();
    }
}

Note

• bfs로 한 번만 행렬을 탐색하는 것을 dp로 착각하였다. 
• dp는 기저값을 넣고 그 값을 이용해서 점화식 규칙대로 다음 값을 구하는 알고리즘이다.
• 어떻게 bfs를 구현해놓고 dp로 풀었다고 착각할 수가 있는지 황당하다..
• dp에는 현재까지의 '이동 길이'가 아닌 현재 좌표로 도달할 수 있는 '경로의 수'를 저장하는 것이다.
• 이 부분을 착각하고 있어서 이해하는 데 시간이 오래 걸렸다. 
• 이전에 비슷한 문제를 푼 적이 있었는데, 이 문제로 다시 한 번 복기되었다.