[백준] 1513 경로 찾기 - Java

 

 

 

문제 출저

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

1513번: 경로 찾기

 

 

 

문제 풀이

DP문제로 점화식을 세워야 합니다. 

 

dp[y][x][count][number]

 

y : y 축 좌표

x : x 축 좌표

count : 이 때까지 만난 오락실 수

number : 최근 만난 오락실 수 

 

 

 

오락실을 만나지 않을 경우

(y-1, x), (y, x-1) 의 경우의 합을 구한다. 

dp[i][j][count][number] = (dp[i][j][count][number] + dp[i][j-1][count][number] + dp[i-1][j][count][number]) % mod;                        }

 

 

오락실을 만났을 경우 

count-1, number를 고려하여 (y-1, x), (y, x-1) 의 경우의 합을 구한다. 

dp[i][j][count][number] = (dp[i][j][count][number] + dp[i][j-1][count][number] + dp[i-1][j][count][number]) % mod;                        }

 

 

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

/*
경로 찾기
https://www.acmicpc.net/problem/1513

알고리즘 설계
dp
각각의 경로 구함
다음 경로에 그 구한 것을 더함

즉 매번 할것
n-1, n
n에서 학원


출발지부터 각 학원 저장
각 학원에서 다음 학원 저장

오락실 위치가 (1,1) or (n,m)인 경우 무조건 방문

dp로 문제를 풀어야 한다.

 */

public class Main {

    static int n; // 세로
    static int m; // 가로
    static int c; // 학원
    static int[][] board;
    static int[][][][] dp;
    static int mod = 1_000_007;



    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        board = new int[n+1][m+1];


        // 학원 위치 저장
        for (int index = 1; index <= c; index++) {
            st = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());

            board[y][x] = index;
        }

        // 좌표, 현재까지 방문한 오락실 개수, 가장 최근에 방문한 오락실 번호
        dp = new int[n+1][m+1][c+1][c+1];

        // 출발선이 오락실인 경우
        if (board[1][1] > 0) {
            dp[1][1][1][board[1][1]] = 1;
        }
        else {
            dp[1][1][0][0] = 1;
        }

        for (int i = 1; i < n+1; i++) {
            for (int j = 1; j < m+1; j++) {

                // 오락실이 아닌 경우
                if (board[i][j] == 0) {
                    for (int count = 0; count <= c; count++) {
                        for (int number = 0; number <= c; number++) {
                            dp[i][j][count][number] = (dp[i][j][count][number] + dp[i][j-1][count][number] + dp[i-1][j][count][number]) % mod;                        }
                    }
                }

                // 오락실인 경우
                else {
                    for (int count = 1; count <= c; count++) {
                        for (int number = 0; number < board[i][j]; number++) {
                            dp[i][j][count][board[i][j]] = (
                                    dp[i][j][count][board[i][j]] + dp[i-1][j][count-1][number] + dp[i][j-1][count-1][number]) % mod;
                        }
                    }
                }

            }
        }

        StringBuilder sb = new StringBuilder();
        for (int count = 0; count <= c; count++) {
            int sum = 0;
            for (int number = 0; number <= c; number++) {
                sum = (sum + dp[n][m][count][number]) % mod;
            }
            sb.append(sum).append(" ");
        }
        System.out.println(sb);



    }




}