[백준/JAVA] 10164번: 격자상의 경로

📖 문제

10164번: 격자상의 경로

 

 

 

💡  풀이 방식

• DP

(0,0)부터 O 표시된 칸까지 가는 DP 한 번,O 표시된 칸부터 오른쪽 아래의 점 (N-1, M-1)까지 가는 DP 한 번해서총 2번의 DP를 진행하며 이동 경로의 수를 나타내는 2차원 배열 dp를 채웠다.

 

이 때 dp를 채우기 위한 점화식은 아래와 같다.

dp[i][j] = dp[i-1][j] + dp[i][j-1];	// 오른쪽과 아래쪽으로만 이동가능하다고 했으므로

 

 

(0,0)부터 오른쪽 아래까지 갈 수 있는 서로 다른 경로의 수는 dp[N-1][M-1]에 저장된다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N,M,K;
    static int[][] grid, dp;
    static int ox = 0, oy = 0;  // O 표시된 칸 위치 (초기 위치 : (0,0))
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] str = br.readLine().split(" ");
        N = Integer.parseInt(str[0]);   // 행
        M = Integer.parseInt(str[1]);   // 열
        K = Integer.parseInt(str[2]);   // O 표시된 칸 번호
        
        grid = new int[N][M];
        
        int num = 1;
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < M ; j++) {
                grid[i][j] = num++;
                
                if(grid[i][j] == K) {
                    ox = i;
                    oy = j;
                }
            }
        }
        
        // dp 2번하기
        dp = new int[N][M];
 
        // 1차) (0,0) -> (ox, oy)
        for(int i = 0 ; i <= ox ; i++) {
            for(int j = 0 ; j <= oy ; j++) {
                if(i == 0 || j == 0)
                    dp[i][j] = 1;
                else
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        
        
        // 2차) (ox, oy) -> (n-1, m-1)
        for(int i = ox ; i < N ; i++) {
            for(int j = oy ; j < M ; j++) {
                if(i == ox || j == oy)
                    dp[i][j] = dp[ox][oy];
                else
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        
        System.out.println(dp[N-1][M-1]);
    }
}
 

 

 

➕ 다른 풀이 방식

DFS로도 풀 수 있다고 한다.

[백준] 자바 10164 격자상의 격로

 

[BOJ] 백준 10164번 : 격자상의 경로 (JAVA)

---

💦 어려웠던 점

- 어렵지 않은 문제인데 왜 헤맸지.. 초반에 약간 BFS로 가면서 거리 나타내는 2차원 배열 채워야하나 잠깐 고민했었다..

 

 

 

1회독	2회독	3회독	4회독	5회독
V