[백준, Java] 1513번, 경로 찾기, [DP]

문제 링크

1513번: 경로 찾기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. 세준이는 →, ↓ 방향으로만 이동할 수 있다.

2. 세준이는 (1, 1)에서 시작하여, (N, M)에 학원에 도착해야 합니다.

3. 세준이는 오락실을 들를 수 있으며, 각 오락실은 번호가 존재하며 오름차순으로만 방문이 가능합니다.

4. 0 ~ C개의 오락실을 방문하고 학원에 도착하는 경우의 수를 결과로 출력합니다.

5. 세준이의 집(1, 1)과 학원(N, M)이 오락실일 수 있습니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 점화식을 통해서 학원에 도착했을 때 0 ~ C개의 오락실을 지나는 경우의 수를 탐색합니다.

 

3. 탐색을 통해 얻은 경우의 수를 결과를 출력합니다.

 

 

세준의 학원에 가는 경우의 수(DP)

 

먼저, 오락실을 생각하지 않고 집(1, 1)에서 학원(N, M)까지 가는 경우의 수를 살펴보겠습니다.

 

X	X (↓)	X
X(→)	X	X
X	X	X

 

→, ↓ 방향으로만 움직이기 때문에 해당 구역에 도착하는 경우는 (r-1, c), (r, c-1)이 됩니다.

 

즉, 점화식으로 표현하면

 

DP[i][j] = DP[i-1][j] + DP[i][j-1]

 

 

 

경우의 수를 구하는 방법을 알았으니, 오락실을 고려할 차례입니다.

 

여기서 핵심은, 오락실을 방문할 때 오름차순으로 방문을 해야 한다는 제약이 존재합니다.

 

경우의 수를 구할 때 DP[i-1][j], DP[i][j-1]에 대해서 지금 방문하는 오락실보다 작은 번호의 오락실을 최근에 방문했어야 경우의 수로 인정할 수 있습니다.

 

예를 들어,

 

3번째 오락실을 방문한 경우의 수가 존재하는데, 지금 방문하려는 오락실이 2번째 오락실인 경우 해당 경우의 수는 포함되지 않아야 합니다.

 

 

그래서 그 부분을 고려하기 위해서 DP[i][j][c][k]으로 경우의 수를 저장하였습니다.

 

DP[i][j][c][k] : (i, j) 구역에 방문할 때 오락실을 c번 지났으며, 최근에 방문한 오락실은 k번째이다.

 

위와 같이 작성한다면

 

C번 때 K번째 오락실을 방문하는 경우의 수는

 

DP[i][j][c][k]의 값을 구하려면 해당 DP[i-1][j][c-1][1 ~ (k-1)], DP[i][j-1][c-1][1 ~ (k-1)]의 합이 되어야 합니다.

 

[1 ~ (k-1)] : 오름차순이기 때문에 최근 방문한 오락실 번호가 k보다 작은 번호여야 하기 때문입니다.

 

 

오락실의 경우의 수를 구한 뒤에 동일하게 학원에 도착하는 DP[i-1][j][c][k]에 대해서 경우의 수를 구하시면 됩니다.

 

 

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N = 3

 

M = 2

 

C = 2

 

( X : 빈공간,  O : 오락실)

 

X	X	X
X	O	X
X	O	X

 

2. 점화식을 통해서 학원에 도착했을 때 0 ~ C개의 오락실을 지나는 경우의 수를 탐색합니다.

 

DP[i][j][c][k] : (i, j) 구역에 방문할 때 오락실을 c번 지났으며, 최근에 방문한 오락실은 k번째이다.

 

기본 0개의 오락실을 방문할 때 경우의 수 탐색

 

 

DP[i][j][0][0]

 

X(1)	X(1)	X(1)
X(1)	O(0)	X(1)
X(1)	O(0)	X(1)

 

오락실이 존재하는 공간은 방문하지 않아야 하기 때문에 0이 됩니다.

 

 

기본 1개의 오락실을 방문할 때 경우의 수 탐색

 

DP[i][j][1][1]

 

1번째 오락실 (2 , 2)을 방문하는 경우의 수를 먼저 점화식을 통해 구합니다.

 

DP[2][2][1][1] = DP[1][2][0][0] + DP[2][1][0][0] = 1 + 1 = 2

 

X(0)	X(0)	X(0)
X(0)	O(2)	X
X(0)	O(0)	X

 

 

(3, 2)가 0인 이유는 2번째 오락실을 방문하면 2개의 오락실이 방문되는 것이기 때문에 해당 구역을 방문하지 않는 경우의 수를 구해야 합니다.

 

오락실에 대한 정보를 구했으니, 기존 경우의 수를 구하는 점화식을 이용해서 구합니다.

 

X(0)	X(0)	X(0)
X(0)	O(2)	X(2)
X(0)	O(0)	X(2)

 

DP[i][j][1][2]

 

1번째 오락실 (3 , 2)을 방문하는 경우의 수를 먼저 점화식을 통해 구합니다.

 

DP[3][2][1][2] = DP[2][2][0][0] + DP[3][1][0][0] = 0 + 1 = 1

 

X(0)	X(0)	X(0)
X(0)	O(0)	X(0)
X(0)	O(1)	X

 

 

(2, 2)가 0인 이유는 위와 같습니다.

 

오락실에 대한 정보를 구했으니, 기존 경우의 수를 구하는 점화식을 이용해서 구합니다.

 

X(0)	X(0)	X(0)
X(0)	O(0)	X(0)
X(0)	O(1)	X(1)

 

기본 2개의 오락실을 방문할 때 경우의 수 탐색

 

DP[i][j][2][2]

 

※ 2개의 오락실을 방문하려면 최소 2번째 오락실까지는 방문해야 하기 때문에 1번째 오락실에 대한 경우는 탐색하지 않아도 됩니다.

 

2번째 오락실 (3, 2)을 방문하는 경우의 수를 먼저 점화식을 통해 구합니다.

 

DP[3][2][2][2] = DP[2][2][1][1] + DP[3][1][1][1] = 2 + 0 = 2

 

X(0)	X(0)	X(0)
X(0)	O(0)	X(0)
X(0)	O(2)	X

 

 

오락실에 대한 정보를 구했으니, 기존 경우의 수를 구하는 점화식을 이용해서 구합니다.

 

X(0)	X(0)	X(0)
X(0)	O(0)	X(0)
X(0)	O(2)	X(2)

 

 

 

3. 탐색을 통해 얻은 경우의 수를 결과를 출력합니다.

 

오락실을 방문하는 0~C개일 때 경우의 수를 탐색한 경우의 수를 기준으로 구하면

 

오락실을 0번 방문할 때

 

DP[N][M][0][0] = 1개

 

오락실을 1번 방문할 때

 

DP[N][M][1][1] + DP[N][M][1][2] = 2 + 1 = 3

 

오락실을 2번 방문할 때

 

DP[N][M][2][2] = 2

 

1 3 2 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 통해 오락실 정보를 띄어쓰기 기준 나누었습니다.
• init함수를 통해서 오락실 0개를 지났을 때 학원의 도착하는 경우의 수를 구합니다.
• setArcadesValue함수를 통해서 1 ~ C개의 오락실을 지났을 때 경우의 수를 구합니다.
• 탐색을 통해 얻은 정보를 기반으로 0~C개의 오락실을 지났을 때 경우의 수를 결과로 BufferdWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• init함수는 경우의 수 점화식을 통해 DP[i][j][0][0]을 탐색합니다.
• init함수에서는 오락실인 경우 0으로 저장합니다.
• search함수는 DP[i][j][c][k]의 경우의 수를 점화식을 통해 탐색합니다.
• search함수는 오락실 경우의 수를 저장한 뒤 학원에 가는 점화식을 통해 탐색합니다.

결과코드

import java.io.*;
import java.util.*;
public class Main {
    //오락실 위치 정보 관련 클래스
    static class Pos{
        int r, c;
        Pos(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
    static int N, M, C;
    //오락실 정보 배열
    static Pos[] arcades;
    //DP[i][j][c][k] 배열
    static int[][][][] DP;
    //2차원 구역 오락실 존재 유므 배열
    static boolean[][] isArcades;
    static final int MOD = 1000007;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        arcades = new Pos[C+1];
        isArcades = new boolean[N+1][M+1];
        DP = new int[N+1][M+1][C+1][C+1];
        DP[1][0][0][0]= 1;
        //오락실 정보 저장
        for(int i=1;i<=C;i++){
            st = new StringTokenizer(br.readLine()," ");
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            arcades[i] = new Pos(r, c);
            isArcades[r][c] = true;
        }
        //DP[i][j][0][0]일 때 구하기
        init();

        //DP[i][j][c][k] 구하기.
        for(int i=1;i<=C;i++){
            for(int j=i;j<=C;j++){
                setArcadesValue(i, j);
            }
        }

        // 0 ~ C번 오락실 방문할 때 경우의 수 BufferedWriter 저장
        for(int i=0;i<=C;i++){
            int sum = 0;
            for(int j=i;j<=C;j++){
                sum = (sum + DP[N][M][i][j]) % MOD;
            }
            bw.write(String.valueOf(sum));
            bw.write(" ");
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //DP[i][j][0][0], 오락실 0개일 때 경우의 수 구하는 함수
    static void init(){
        for(int i=1;i<=N;i++){
            for(int j=1;j<=M;j++){
                if(isArcades[i][j]){
                    continue;
                }
                DP[i][j][0][0] = (DP[i-1][j][0][0] + DP[i][j-1][0][0]) % MOD;
            }
        }
    }

    //DP[i][j][c][k]에 대해 점화식을 통해 경우의 수 구하기.
    static void setArcadesValue(int h, int c){
        Pos cur = arcades[c];

        //DP[i][j][c][k] = DP[i-1][j][c-1][1~(k-1)] + DP[i][j-1][c-1][1 ~ (k-1)]
        //h-1부터 시작하는 이유는 c-1번째는 최소 c-1번째 오락실을 이용해야 하기 때문입니다.
        for(int i=h-1;i<c;i++){
            DP[cur.r][cur.c][h][c] += (DP[cur.r-1][cur.c][h-1][i] + DP[cur.r][cur.c-1][h-1][i]) % MOD;
        }


        //오락실 정보 저장한 뒤, 학원 도착하는 경우의 수 구하기.
        for(int i=cur.r; i<=N;i++){
            for(int j=cur.c;j<=M;j++){
                if(isArcades[i][j]){
                    continue;
                }
                DP[i][j][h][c] = (DP[i-1][j][h][c] + DP[i][j-1][h][c]) % MOD;
            }
        }
    }
}