문제링크:https://www.acmicpc.net/problem/1520
1520번: 내리막 길
여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지
www.acmicpc.net
어려운 문제였습니다. 기존 dp와는 많이 달라서 저도 해맸습니다. ㅠㅠ
우선 문제를 보자마자 완전탐색문제구나 인식하실 수 있습니다.
이때 n=500, m=500 까지 가능합니다. 일반적인 dfs, bfs로 푸실 경우
최악의 경우에는 4^500*500 번까지 연산이 진행되기 때문에 일반적인 방법으로는 풀 수 없었습니다.
답은 dp적인 관점으로 기존에 탐색한 경로의 값을 가지고, 해당 좌표에 방문하면 해당값을 반환하는 형태로 dfs를 구현하는 것입니다. 즉 dp의 up-down 방식과 dfs 방식을 합쳐서 답을 구해야 합니다.
즉 깊이 우선 탐색을 하면서 탐색한 값을 이전 함수에 전달해주면서 결과 값을 도출합니다.
도착지에 도착하면 그 이전함수에 값들을 전달해주면서 더해주어 dp[1,1]에서 결과값을 찾는 것 입니다.
우선 해당관점을 생각하는거 자체가 어렵고, 구현난이도는 높지않습니다.
int dfs(int cy, int cx) {
if (cy == m && cx == n) {
//dp[cy][cx] = 1;
return 1; //종점이라면 1을 반환합니다.
}
if (dp[cy][cx]) //이미 방문한 곳이라면 해당 dp값을 전달해준다.
return dp[cy][cx];
for (int i = 0; i < 4; i++) {
int next_y = cy + y_ar[i];
int next_x = cx + x_ar[i];
if (next_y > 0 && next_y <= m && next_x > 0 && next_x <= n)
if (arr[cy][cx] > arr[next_y][next_x])
dp[cy][cx] += dfs(next_y, next_x);
}
return dp[cy][cx];
}
1. 출발점에서 dfs를 시작해서 종점에 도착하면 1을 반환한다.
2. 만약 이미 방문한 곳이라면 탐색하지 않고 기존값을 전달합니다.
3. 두 경우가 아니라면 상하좌우를 탐색하며 해당 좌표로 이동할 수 있는지 확인하여 줍니다.
위 식에서 한가지 간과하게 있습니다. 만약 dp값이 0이여도 이미 탐색한 경우했을 수 있다는 것을 간과했습니다. 따라서 visited 배열을 하나더 만들어서 방문했는지 여부를 따로 판단해주어야 합니다.
아래는 정답코드입니다.
#include <iostream>
using namespace std;
int arr[501][501]= {};
int dp[501][501] = {};
bool visited[501][501] = { 0 };
int m, n;
int y_ar[4] = { 1, 0, -1, 0 };
int x_ar[4] = { 0, 1, 0, -1 };
int dfs(int cy, int cx) {
if (cy == m && cx == n) {
//dp[cy][cx] = 1;
return 1; //종점이라면 1을 반환합니다.
}
if (visited[cy][cx]) //이미 방문한 곳이라면 해당 dp값을 전달해준다.
return dp[cy][cx];
visited[cy][cx] = 1;
for (int i = 0; i < 4; i++) {
int next_y = cy + y_ar[i];
int next_x = cx + x_ar[i];
if (next_y > 0 && next_y <= m && next_x > 0 && next_x <= n)
if (arr[cy][cx] > arr[next_y][next_x])
dp[cy][cx] += dfs(next_y, next_x);
}
return dp[cy][cx];
}
int main() {
cin.tie(NULL);
ios::sync_with_stdio(false);
cin >> m >> n;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
cin >> arr[i][j];
cout << dfs(1, 1)<< '\n';
return 0;
}
걍 문제자체가 어려웠습니다.. 코드를 보고도 설명이 이해가 가지 않으신다면 아래 링크를 참고해보세요.
https://wootool.tistory.com/83
[백준][1520번][DP] 내리막길
내리막길 https://www.acmicpc.net/problem/1520 <코드> 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..
wootool.tistory.com