[백준 1520] 내리막 길

문제 보러가기

한번에 성공해서 기분이 좋다 ㅎ.

• 참고
  • 경로는 정해져 있다. 사실상 단방향 Acyclic Graph 문제이다.

내가 푼 방법

Priority Queue + DP. 나는 순방향으로 (0,0)에서 시작해서 점진적으로 값이 업데이트 되는 방법을 사용했다. dp 배열의 의미는 다음과 같다.

dp[a][b] = “(0,0)부터 (a,b)까지 경로의 수”

이 배열을 (0,0)부터 시작해서 (M-1,N-1)까지 차례로 구해나가는 방법을 썼다.

중간 문제점

처음에는 Queue를 사용하려고 하였다. 이러면 문제가 발생했다. 분명 dp[a][b]는 (0,0)부터 (a,b)까지의 ‘최종적인’ 경로의 수를 담고 있어야 하는데, 단순히 큐를 이용하면 이 정보를 담지 못하게 되는 경우가 발생했다.

여기서 큐가 1 다음에 [3,2]순으로 되어 있다고 생각해보자. 3을 먼저 꺼내서 (그림에는 없지만) 인접 노드들에 대해서 경로를 업데이트한다. 그 다음에는 2를 꺼내서 인접 노드들을 업데이트한다. 문제는 2의 인접노드 중 하나가 3이므로, 3이 다시 큐에 푸쉬되어 동일한 연산을 반복한다는 것이다. 이 문제를 막기 위해서 priority queue를 사용했다. 2의 높이는 3의 높이보다 크다. priority queue는 노드의 높이 기준, 내림차순으로 설정했다. 이러면 [2,3]으로 설정되어 3 노드를 중복으로 방문하지 않게 된다.

다른 사람들 대부분의 풀이

DFS + DP

대부분의 풀이를 보니 (M-1,N-1)에서부터 시작해 (0,0)으로 (역방향으로) 퍼져나가는 방법을 사용했더라. 이게 조금 더 뭔가 안정적인 방법처럼 보이기는 했다. 이때의 dp 정의는 다음과 같다.

dp[a][b] = “(a,b)부터 (M-1,N-1)까지 경로의 개수”

dp 배열을 -1과 같은 값으로 초기화 해놓고

• 초기값이면 DFS를 이용해 탐색
• 이미 탐색했던 값이면 dp 배열 이용

이러한 식으로 계속 업데이트 해나가는 방식이다. 문제를 조금만 꼬았으면 내 방식으로는 못풀지 않았을까 싶긴 한 것 같다

코드

코드 보기

/*
1520 : 내리막 길
DP 문제
*/

#include <iostream>
#include <vector>
#include <queue>
#define ull unsigned long long
#define pii pair<int, int>
using namespace std;

/*
경로의 수를 저장하는 DP 배열
dp[i][j] = (i,j)까지의 경로의 수를 나타낸다
*/
ull dp[600][600] = {
	0,
};
int M = 0, N = 0;
vector<vector<ull>> map;
vector<vector<bool>> visited;
struct comp
{
	bool operator()(pii &a, pii &b)
	{
		return map[a.first][a.second] < map[b.first][b.second];
	}
};

/*
높이 내림차순 기준 우선순위 큐
*/
priority_queue<pii, vector<pii>, comp> pq;
int cnt = 0;
void traverse(int i, int j)
{
	pq.push(make_pair(i, j));
	while (!pq.empty())
	{
		// cnt++;
		int x = 0, y = 0;
		x = pq.top().first;
		y = pq.top().second;
		pq.pop();

		if (visited[x][y] == true)
			continue;
		visited[x][y] = true;

		// 	현재 높이를 저장
		ull cur_height = 0;
		cur_height = map[x][y];

		int dx[4] = {-1, 1, 0, 0};
		int dy[4] = {0, 0, 1, -1};

		for (int d = 0; d < 4; d++)
		{
			int next_x = 0, next_y = 0;
			next_x = x + dx[d];
			next_y = y + dy[d];

			// 인덱스를 벗어난 곳은 그냥 통과한다
			if (next_x < 0 || next_x >= M || next_y < 0 || next_y >= N)
				continue;

			// 내리막길이라면
			if (cur_height > map[next_x][next_y])
			{
				// 경로의 개수를 전파한다
				dp[next_x][next_y] += dp[x][y];
				// 우선순위 큐에 저장한다
				pq.push(make_pair(next_x, next_y));
			}
		}
		// cout << "cnt = " << cnt << "\n";
		// for (int i = 0; i < M; i++)
		// {
		// 	for (int j = 0; j < N; j++)
		// 		cout << dp[i][j] << " ";
		// 	cout << "\n";
		// }
		// cout << "\n=====================\n";
	}
}

int main()
{
	cin >> M >> N;

	// init map
	for (int i = 0; i < M; i++)
	{
		vector<ull> row;
		vector<bool> row_visited;
		for (int j = 0; j < N; j++)
		{
			ull input;
			cin >> input;
			row.push_back(input);
			row_visited.push_back(false);
		}
		map.push_back(row);
		visited.push_back(row_visited);
	}

	dp[0][0] = 1;
	traverse(0, 0);

	cout << dp[M - 1][N - 1];
}