https://www.acmicpc.net/problem/1520
걸린 시간 : 32분 21초
알고리즘
처음엔 간단한 DFS로 접근했다가 시간초과가 났다. 그제서야 시간복잡도를 체크해보니 최대 4^(500*500) 번의 실행이 일어날 수 있었다. 따라서 다른 방법을 찾아야 했다.
바로 떠올린 것이 DP였다. 예제를 다시 따라해보니 같은 실행을 너무 과도하게 반복한다는 생각이 들었다.
DP에서 제일 중요한 것은 일반항이다. 잘 적용할 수 있는 일반항을 생각해보았다.
pathcnt[i][j] 의 의미를 "(i, j) 에서 (M, N)까지 갈 수 있는 가짓수"로 생각할 수 있었다. 이러면 pathcnt[0][0]이 답이 될 것이다.
하지만, 기존에 많이 하던 방식으로 이 문제를 해결하려고 생각하니 또 뭔가 잘 안됐다... bottom up 방식으로 접근한다면, "어떤 지점부터 먼저 계산해야할 것인가" 가 문제였다. 따라서 top down 방식으로 해야 한다고 생각했다.
pathcnt 배열을 모두 -1로 초기화하고 가짓수를 알아냈을 땐 0이상의 수를 대입해서 중복된 계산을 하지 않도록 했다.
정답 코드
#include <bits/stdc++.h>
using namespace std;
int M, N;
int board[501][501];
int pathcnt[501][501];
int di[4] = {-1, 0, 0, 1};
int dj[4] = {0, -1, 1, 0};
int bfs (int ci, int cj) {
if (ci == M-1 && cj == N-1) {
return 1;
}
if (pathcnt[ci][cj] != -1) {
return pathcnt[ci][cj];
}
int ret = 0;
for (int k = 0; k < 4; k++) {
int ni = ci + di[k];
int nj = cj + dj[k];
if (ni < 0 || ni >= M || nj < 0 || nj >= N)
continue;
if (board[ni][nj] < board[ci][cj]) {
ret += bfs(ni, nj);
}
}
pathcnt[ci][cj] = ret;
return ret;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> M >> N;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
cin >> board[i][j];
}
}
for (int i = 0; i < M; i++) {
fill(pathcnt[i], pathcnt[i] + N, -1);
}
bfs(0, 0);
cout << pathcnt[0][0];
return 0;
}
'Baekjoon Online Judge' 카테고리의 다른 글
[BOJ] 1941: 영역 구하기 (Java) (0) | 2023.10.19 |
---|---|
[BOJ] 1941: 소문난 칠공주 (Java) with 조합 (0) | 2023.10.19 |
[BOJ] 11404 : 플로이드 (C++) with 플로이드 (1) | 2023.10.04 |
[BOJ] 14501 : 퇴사 (C++) with DP (1) | 2023.09.27 |
[BOJ] 20056: 마법사 상어와 파이어볼 (C++) (1) | 2023.09.27 |