[백준][BOJ][C++][1520번] 내리막 길

문제

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

 

 

코드

#include<iostream>
#include<memory.h>
using namespace std;
 
int N, M;
int ans;
int map[501][501];
int visited[501][501];
int p_x[4] = { 0,1,0,-1 };
int p_y[4] = { 1,0,-1,0 };
 
void printt(int cnt) {
    cout << cnt << "번째 " << endl;
    for (int y = 0; y < M; y++) {
        for (int x = 0; x < N; x++) {
            cout << visited[y][x] << " ";
        }
        cout << endl;
    }
    cout << endl;
}
 
int dfs(int f_x, int f_y, int cnt) {
    //printt(cnt);
    if (f_x == N - 1 && f_y == M - 1) return 1;
    if (visited[f_y][f_x] == -1){ 
        visited[f_y][f_x] = 0;
 
    for (int i = 0; i < 4; i++) {
        int n_x = f_x + p_x[i];
        int n_y = f_y + p_y[i];
        if (n_x >= N || n_x < 0 || n_y >= M || n_y < 0) continue;  //범위를 벗어나면 통과    
        //if (visited[n_y][n_x]) return visited[n_y][n_x]; //이미 방문한 곳 통과
        //cout << "방문할곳의 위치 : " << n_y << "," << n_x <<","<< map[n_y][n_x] <<"  현재 위치 :" << f_y << "," << f_x <<","<< map[f_y][f_x] << endl;
        if (map[n_y][n_x] >= map[f_y][f_x]) continue; //방문할곳이 더 높으면 통과
        visited[f_y][f_x] += dfs(n_x, n_y, cnt + 1);
    }
}
    return visited[f_y][f_x];
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> M >> N;
    for (int y = 0; y < M; y++) {
        for (int x = 0; x < N; x++) {
            cin >> map[y][x];
        }
    }
    memset(visited, -1, sizeof(visited));
    //dfs(0,0,0,0);
    dfs(0, 0,0);
    cout << visited[0][0];
}

풀이

처음에는 dfs만을 이용하여 풀이를 하였더니 시간초과가 발생하였습니다. 

그래서 가지치기가 더 가능한가를 고민 하다가 더 이상 가지치기는 불가능 하다고 생각하고 다른 방법을 생각하던 중에 dp를 이용하여 풀이를 하였고 그때도 시간초과가 발생하였습니다. 

그래서 어쩔수 없이 검색을 통해 확인을 해 보니 dp를 이용할때 dp 배열을 -1로 초기화를 시켜주어 

-1인 곳에만 접근하도록 진행해야 상하좌우를 확인하는 갯수를 줄일 수 있다는 것을 알게 되었고 바로 저의 소스에 적용시켜주어 문제를 해결하였습니다. 

아래 코드에 dfs만을 이용 했을때와 dp를 이용했지만 배열을 초기화시켜주지 않고 dp를 사용했을때 코드를 올려드리겠습니다.

 

dfs만을 이용하여 짠 코드 (시간초과)

#include<iostream>
using namespace std;
 
int N, M;
int ans;
int map[501][501];
bool visited[501][501];
int p_x[4] = { 0,1,0,-1 };
int p_y[4] = { 1,0,-1,0 };
 
void printt(int cnt) {
    cout << cnt << "번째 " << endl;
    for (int y = 0; y < M; y++) {
        for (int x = 0; x < N; x++) {
            cout << visited[y][x] << " ";
        }
        cout << endl;
    }
    cout << endl;
}
 
void dfs(int f_x, int f_y,int cnt) {
    if (f_x == N - 1 && f_y == M - 1) {
        //printt(cnt);
        ans++;
        return;
    }
    for (int i = 0; i < 4; i++) {
        int n_x = f_x + p_x[i];
        int n_y = f_y + p_y[i];
        if (n_x >= N || n_x<0 || n_y>=M || n_y < 0) continue;  //범위를 벗어나면 통과
        if (visited[n_y][n_x]) continue; //이미 방문한 곳 통과
        //cout << "방문할곳의 위치 : " << n_y << "," << n_x <<","<< map[n_y][n_x] <<"  현재 위치 :" << f_y << "," << f_x <<","<< map[f_y][f_x] << endl;
        if (map[n_y][n_x] >= map[f_y][f_x]) continue; //방문할곳이 더 높으면 통과
        visited[n_y][n_x] = true;
        dfs(n_x, n_y,cnt+1);
        visited[n_y][n_x] = false;
        
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> M >> N;
    for (int y = 0; y < M; y++) {
        for (int x = 0; x < N; x++) {
            cin >> map[y][x];
        }
    }
    //dfs(0,0,0,0);
    visited[0][0] = true;
    dfs(0, 0,0);
    cout << ans;
}

 

dp를 초기화 해주지 않고 짠 코드 (시간초과)

#include<iostream>
using namespace std;
 
int N, M;
int ans;
int map[501][501];
int visited[501][501];
int p_x[4] = { 0,1,0,-1 };
int p_y[4] = { 1,0,-1,0 };
 
void printt(int cnt) {
    cout << cnt << "번째 " << endl;
    for (int y = 0; y < M; y++) {
        for (int x = 0; x < N; x++) {
            cout << visited[y][x] << " ";
        }
        cout << endl;
    }
    cout << endl;
}
 
int dfs(int f_x, int f_y,int cnt) {
    //printt(cnt);
    if (f_x == N - 1 && f_y == M - 1) return 1;
    if (visited[f_y][f_x]) return visited[f_y][f_x];
 
    for (int i = 0; i < 4; i++) {
        int n_x = f_x + p_x[i];
        int n_y = f_y + p_y[i];
        if (n_x >= N || n_x<0 || n_y>=M || n_y < 0) continue;  //범위를 벗어나면 통과    
        //if (visited[n_y][n_x]) return visited[n_y][n_x]; //이미 방문한 곳 통과
        //cout << "방문할곳의 위치 : " << n_y << "," << n_x <<","<< map[n_y][n_x] <<"  현재 위치 :" << f_y << "," << f_x <<","<< map[f_y][f_x] << endl;
        if (map[n_y][n_x] >= map[f_y][f_x]) continue; //방문할곳이 더 높으면 통과
        visited[f_y][f_x]+=dfs(n_x, n_y,cnt+1);
    }
    return visited[f_y][f_x];
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> M >> N;
    for (int y = 0; y < M; y++) {
        for (int x = 0; x < N; x++) {
            cin >> map[y][x];
        }
    }
    //dfs(0,0,0,0);
    dfs(0, 0,0);
    cout << visited[0][0];
}