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

그래프 탐색 + 다이나믹 프로그래밍 문제

사실 이 문제를 본 건 엄청 오래 전이였는데, 그 당시엔 못 풀었었다. (검색도 했었는데, 그냥 이렇게 푸는거구나. 만 알고 넘어감. 바로 풀면 의미가 없으므로!)

이번에 학교에서 주최한 프로그래밍 대회에서 비슷한 문제를 봤었는데, 이 문제에 대한 기억이 떠올라서

검색해서 비슷한 문제를 맞춘 후에 다시 풀어봤다.

그래프 탐색 이론과 DP (Top-Down)방식을 사용하는 문제가 있다니 신기했다.

 

문제풀이

결국, (1, 1)에서 (M, N)까지 몇 개의 길이 있는지를 구하는 문제다.

나는 지금까지 DP는 Bottom-Up 위주로 많이 풀었었는데 이 문제는

지금 (1, 1)에서 알 수 있는 경우의 수가 없다.

그런데 (M, N)에서 (M, N)으로 가는 경우의 수는 1가지이다.

(M, N)에 대한 조건을 알고 있으므로

(M, N), (M - 1, N), (M, N - 1), ... , (1, 1)이런 순서로 갱신해주면 된다.

 

• 만일 한 정점을 한번이라도 방문한 경우. 해당 정점에서 (M, N)으로 가능 경로의 수는 이미 업데이트 된 상황이다. (Top-Down 방식의 당연한 소리)
• 방문하지 않은 정점의 경우, 해당 정점에서 상, 하, 좌, 우 중 높이가 더 낮은 곳으로 이동한다.

나는 DFS + DP로 해당 문제를 풀어봤다.

#include <iostream>
using namespace std;

int height, width;
int board[501][501];
int dp[501][501];
bool visit[501][501]; // 틀린이유. 해당 칸이 아예 0일 수 있다. 나는 칸의 값이 0이라면 방문하지 않은 것으로 생각해서 틀림.
pair<int, int> direction[4] = {
	{-1, 0},
	{1, 0},
	{0, -1},
	{0, 1}
};

int go(int r, int c, int prev) {
	if (r < 1 || r > height || c < 1 || c > width) { return 0; }

	if (board[r][c] >= prev) { return 0; }

	if (r == height && c == width) { return 1; }

	if (visit[r][c]) { return dp[r][c]; }

	visit[r][c] = true;

	for (pair<int, int> dir : direction) {
		int nxtR = r + dir.first;
		int nxtC = c + dir.second;
		dp[r][c] += go(nxtR, nxtC, board[r][c]);
	}

	return dp[r][c];

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> height >> width;

	for (int i = 1; i <= height; i++) {
		for (int j = 1; j <= width; j++) {
			cin >> board[i][j];
		}
	}

	go(1, 1, 10001);

	cout << dp[1][1];

	return 0;
}

처음에 높이와 너비를 입력받고 각 칸의 수를 입력받는다.

 

그리고 go() 메서드를 실행한다. go() 메서드는 DFS + Top-Down 이라고 생각하면 된다.

go()메서드의 매개변수는 순차적으로 (행, 열, 이전 칸의 숫자) 이다.

고려해주는 조건은 다음과 같다.

• 범위 벗어난 경우 0 return
• 이전 칸의 숫자보다 현재 칸의 숫자가 큰 경우 0 return
• (M, N)인 경우 1 return
• 현재 탐사중인 칸을 이전에 방문했다면, 현재 칸에서 (M, N)까지 가는 경로의 수를 이미 계산했다는 뜻. dp[r][c] return

위 조건에 걸리지 않는다면 상, 하, 좌, 우 방향으로 탐사를 해서 각 칸마다 갈 수 있는 경로의 수를 다 더해서 현재 칸에 더해준다. 그리고 현재 칸을 방문처리한 후에 dp[r][c]를 return 해준다.

 

방문했다는 처리를 dp[r][c] == 0이라는 조건으로 처음 설정했는데 이렇게 하면

만일 실제로 (M, N)까지 가는 경로가 0인 칸은 계속해서 상, 하, 좌, 우를 탐사하게 된다.

따라서 그냥 visit 배열을 만들어서 방문처리를 해주었다. 이것 때문에 한 번 시간초과가 났다.

 

1달 전의 코드를 보면 BFS로 풀려고 하다가 시간 초과가 났고,

오늘 푼 코드는 방문 처리를 못해서 시간 초과가 났다.

그래프 탐색 + DP. 정말 신기한 문제였다.

굳이 따지자면 DP 쪽이 좀 더 가까운 것 같다.

 

GitHub - kimyunseok/cpp: my study-record

코드 전문은 위에서 확인이 가능하다.