[BOJ] 백준 10164. 격자상의 경로

문제

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

 

 

 

---

풀이

고등학교? 때 배웠던 격자 상의 경로를 찾는 아이디어를 통해 문제를 해결했습니다.

출처 : https://blog.naver.com/jihoon0023/120164925602

 

격자 상의 출발지와 목적지를 정해 행렬을 만드는 방식으로 구현을 했습니다.

 

 행렬을 만드는 메서드에는 시작점과 도착점, 그리고 특정 경로를 거치면  재귀를 통해 그 포인트부터 행렬을 생성할 수 있게끔 check 변수를 매개변수로 넣어주었습니다. 

 

아래는 소스 코드입니다.

 

---

소스 코드

import java.util.Scanner;

public class B10164_격자상의경로 {

    static int N,M;
    static int[][] dp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        int mark = sc.nextInt();
        dp = new int[N][M];
        if(mark == 0){
            makeMatrix(1,0,0,N,M,0);
        }
        else {
            int markRow = (mark - 1) / M;
            int markCol = (mark - 1) % M;
            makeMatrix(1,0,0,markRow+1,markCol+1,1);
        }
        System.out.println(dp[N-1][M-1]);
    }
    
    static void makeMatrix(int init, int row, int col, int R, int C, int check){
            for(int r=row;r<R;r++){
                dp[r][col] = init;
            }
            for(int c=col;c<C;c++){
                dp[row][c] = init;
            }

            for(int r=row+1;r<R;r++){
                for(int c=col+1;c<C;c++){
                    dp[r][c] = dp[r-1][c]+dp[r][c-1];
                }
            }
            int nextInit = dp[R-1][C-1];
            if(check==1) makeMatrix(nextInit, R-1, C-1, N, M, 0);
    }
}