백준 1520_내리막 길 문제풀이 in C++
문제 URL
https://www.acmicpc.net/problem/1520
문제 요구사항
- 여행을 떠난 세준이는 지도를 하나 구하였다.
- 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다.
- 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.
- 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다.
- 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다.
- M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.
- 첫째 줄에 이동 가능한 경로의 수 H를 출력한다.
- 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.
접근 방법
- 일반적인 dfs로 탐색하되, 만약 두 갈래 이상의 내리막 길이 나온다면 어떻게 할 것인지 잘 생각해보면 된다.
- DP를 통해 해당 경로가 이미 visited이고, 해당 경로가 목적지까지 갈 수 있다면 최종적으로 1을 반환해서 dp 값을 해당 루트 값에 + 1을 한다.
- 그러면 최종적으로 0, 0 (시작점)에서부터 모든 경로가 시작되므로, 해당 좌표에 목적지까지 갈 수 있는 경로의 수가 누적해서 쌓이게 된다.
풀이 순서
- N과 M 맵의 정보를 입력받는다.
- DFS ( 0, 0 ) 수행
- 현재 x, y 좌표가 각각 N - 1, M - 1과 같다면 1을 return 한다.
- 현재 x, y 좌표가 visited라면, 해당 좌표의 checked를 반환 한다.
- visited x y좌표에 true 값을 넣고, nx ny를 구한다. 이 때, map nx ny의 좌표 값이 현재 좌표 x y의 값보다 작다면, checked의 x y 좌표 값에 checked x y 좌표 값 + dfs ( nx , ny)를 한다.
- dx dy 탐색 종료 후, checked x y (0, 0)을 반환한다.
- 반환 된 값 출력
소스코드
#include <iostream>
#include <queue>
using namespace std;
int M, N;
int map[500][500] = { 0, };
bool visited[500][500] = { false, };
long long checked[500][500];
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
long long res = 0;
void input() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> map[i][j];
}
}
}
int dfs(int x, int y) {
if (x == N - 1 && y == M - 1)
return 1;
if (visited[x][y])
return checked[x][y];
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
if (map[nx][ny] < map[x][y]) {
checked[x][y] = checked[x][y] + dfs(nx, ny);
}
}
}
return checked[x][y];
}
void solution() {
res = dfs(0, 0);
}
void output() {
cout << res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
input();
solution();
output();
return 0;
}
문제 풀이 결과
