[백준/JAVA] 10164번: 격자상의 경로
📖 문제
10164번: 격자상의 경로
입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으
www.acmicpc.net
💡 풀이 방식
• 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]에 저장된다.
🔺 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
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]);
}
}
|
cs |
➕ 다른 풀이 방식
DFS로도 풀 수 있다고 한다.
[백준] 자바 10164 격자상의 격로
문제 행의 수가 N이고 열의 수가 M인 격자의 각 칸에 1부터 N×M까지의 번호가 첫 행부터 시작하여 차례로 부여되어 있다. 격자의 어떤 칸은 ○ 표시가 되어 있다. (단, 1번 칸과 N × M번 칸은 ○ 표
kjs-dev.tistory.com
[BOJ] 백준 10164번 : 격자상의 경로 (JAVA)
문제 행의 수가 N이고 열의 수가 M인 격자의 각 칸에 1부터 N×M까지의 번호가 첫 행부터 시작하여 차례로 부여되어 있다. 격자의 어떤 칸은 ○ 표시가 되어 있다. (단, 1번 칸과 N × M번 칸은 ○ 표
steady-coding.tistory.com
💦 어려웠던 점
- 어렵지 않은 문제인데 왜 헤맸지.. 초반에 약간 BFS로 가면서 거리 나타내는 2차원 배열 채워야하나 잠깐 고민했었다..
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V |