코딩공작소

[백준]내리막길 본문

알고리즘/DP

[백준]내리막길

안잡아모찌 2019. 10. 10. 10:46

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

 

1520번: 내리막 길

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지

www.acmicpc.net

처음에는 dfs로 풀었었다... 하지만 맵의 크기가 500X500.. 상하좌우.. 즉 4^(500x500) ... 당연히 시 간 초 과

DP로 풀어야겠다고 생각했고 DP의 개념과 메모이제이션에 대해서 제대로 알게되었다.

(전글참고)

 

<시간초과 코드>

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
#include <iostream>
#include <cstring>
using namespace std;
 
int N, M;
int map[500][500];
int isV[500][500];
int dr[] = { 1,-1,0,0 }, dc[] = { 0,0,1,-1 };
int cnt = 0;
 
void dfs(int r, int c) {
    if (r == N - 1 && c == M - 1) {
        cnt++;
        return;
    }
 
    for (int i = 0; i < 4; i++) {
        int nr = r + dr[i], nc = c + dc[i];
        if (nr < 0 || nc < 0 || nr >= N || nc >= M || map[nr][nc] >= map[r][c]) continue;
        
        if (isV[nr][nc] == 0 ) {
            isV[nr][nc] = 1;
            dfs(nr, nc);
            isV[nr][nc] = 0;
        }
    }
 
}
 
int main()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) cin >> map[i][j];
    dfs(0, 0);
    printf("%d\n", cnt);
    return 0;
}
 
 cs

 

 

<DP+DFS코드>

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
#include <iostream>
#include <cstring>
using namespace std;
 
int N, M;
int map[500][500], DP[500][500];
int dr[] = { -1,1,0,0 }, dc[] = { 0,0,-1,1 };
 
int dfs(int r, int c) {
    if (DP[r][c] != -1) return DP[r][c];
    if (r == 0 && c == 0) return 1;
    DP[r][c] = 0;
    for (int i = 0; i < 4; i++) {
        int nr = r + dr[i], nc = c + dc[i];
        if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
        if (map[nr][nc] > map[r][c]) DP[r][c] += dfs(nr, nc);
    }
    return DP[r][c];
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> M;
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) cin >> map[i][j], DP[i][j] = -1;
    printf("%d\n", dfs(N - 1, M - 1));
    return 0;
}
cs
저작자표시 비영리 (새창열림)

'알고리즘 > DP' 카테고리의 다른 글

[프로그래머스]정수삼각형  (0) 2019.10.26
DP,메모이제이션  (0) 2019.10.10
[백준]점프  (0) 2019.10.09
[SWEA]수영장  (0) 2019.08.18
[백준]퇴사(두번째 풂)  (0) 2019.07.11
'알고리즘/DP' Related Articles more