[백준] Baekjoon#1520 내리막 길

문제 출처: https://www.acmicpc.net/problem/1520

문제 간단한 요약

n x m 배열에서 (0, 0)에서 (n-1, m-1)까지 가는 경로의 개수를 찾는다.

가는 방법은 점점 값이 낮아지는 방향으로만 이동할 수 있고 상하좌우 방향으로만 이동 가능하다.

문제 접근

가장 먼저 떠오른 풀이 방법은 dfs였다. 물론 해당 문제에서는 경로만 다르면 들린 정점을 또 들릴 수 있어서 그냥 아무 처리를 안 하고 브루트포스 방식으로 풀면 당연히 시간 초과가 난다.

따라서 방문한 정점을 또 들리지 않도록 잘 처리를 하면서 dfs를 하면 된다고 생각했다가 다른 풀이 방법이 떠올라서 dfs는 선택하지 않았다.

항상 내려가야한다에 초점을 맞춰보기로 했다.

예를 들어서 (0, 0)의 값이 50이면 다시는 50 이상의 칸은 지나지 않는다는 것을 알 수 있다. 따라서 내가 갈 수 있는 위치 중에서 가장 큰 값을 갖는 곳을 우선적으로 선택하면서(약간 최소 신장 트리의 최대 신장 버전) 진행하면 중복이 발생하지 않을 거라 생각했다. 

또한 무조건 높이가 높은 칸을 먼저 들리기 때문에 경로가 다양하더라도 특정 칸을 들리기 전에 해당 칸에 올 수 있는 모든 경우를 다 세고 해당 칸에 오게된다.

따라서 지금 갈 수 있는 칸 중에서 가장 높은 칸을 선택하고 해당 칸에서 새로 갈 수 있는 칸을 우선순위 큐에 추가하면서 현재 자신의 분기수를 더해주는 방식으로 진행했다.

즉 위의 예시를 한 번 진행해 보자.

Flow

처음에 갈 수 있는 칸은 (0, 0)이고 분기는 1개라고 할 수 있다. 해당 (0, 0)을 선택하고 갈 수 있는 칸을 확인하자 (0, 1)인 45와 (1, 0)인 35 모두 현재의 칸 50보다 작기 때문에 갈 수 있다.

현재칸의 분기만큼을 해당 칸에 더해주고 갈 수 있는 칸에 해당 두 칸을 넣어주자.

이제 갈 수 있는 칸이 두 칸이 되었는데 우리는 지금 갈 수 있는 칸 중에서 가장 큰 값을 선택하기로 했다. 따라서 45인 (0, 1)을 선택하자. 45를 기준으로 새로 갈 수 있는 곳은 37인 (0, 2)밖에 없다. 따라서 (0, 2): 37을 갈 수 있는 칸에 넣어주고 현재 자신의 분기인 1을 더해주자.

이번에도 갈 수 있는 칸은 두 칸이다. 가장 큰 값이 37이니 (0, 2)를 선택하자. 해당 칸에서 갈 수 있는 곳은 32인 (0, 3)밖에 없다 따라서 (0, 3): 32를 갈 수 있는 칸에 넣어주고 자신의 분기를 더해주고 넘어가자.

이번에도 갈 수 있는 칸은 두 칸이고 가장 큰 값은 35다. 드디어 맨 처음 넣어준 (1, 0)을 선택하게 되었다. 해당 칸에서 갈 수 있는 곳은 30 (2, 0)밖에 없다. 이를 갈 수 있는 칸에 넣어주고 분기를 더해주자.

위와 같이 진행하면 (0, 3): 32를 선택하고 해당 칸에서 갈 수 있는 칸이 이번에는 (0, 4): 30과 (1, 3): 20으로 두 칸이다. 두 칸 모두 분기를 더해주고 갈 수 있는 칸에 넣어주자.

이번에 갈 수 있는 칸은 세 칸인데 이 중에서 가장 큰 값은 30이고 두 개나 존재한다. 둘 중에 어떤 것을 먼저 선택해도 상관은 없다. 먼저 (2, 0): 30을 선택했다고 해보자. 그러면 해당 칸에서 갈 수 있는 27을 갈 수 있는 칸에 넣고 분기를 더해주면 된다. 이어서 바로 진행하면 그다음 갈 수 있는 칸도 세 곳이고 30, 27, 20이 존재하고 가장 큰 30을 선택하면 (0, 4): 30에서 갈 수 있는 칸은 25밖에 없고 갈 수 있는 칸에 추가하고 분기를 더해주자.

이번에 선택되는 칸은 27이고 해당 칸에서는 24로만 갈 수 있으니 갈 수 있는 칸에 넣어주고 분기를 더해주자.

이번에 선택될 칸은 (1, 4): 25가 되고 해당 칸에서 갈 수 있는 곳은 20이다. 하지만 (1, 3): 20은 이미 갈 수 있는 칸에 있는 칸이다. 따라서 추가적으로 넣지 않고 분기의 값만 더해준다.

이번엔 (3, 1): 24가 선택되고 추가적으로 22를 갈 수 있게 된다. 분기도 더해주자 또한 이러한 식으로 쭉 진행하면 결국 아래와 같은 상황이 된다.

이번에 (2, 3): 17이 선택되고 갈 수 있는 칸은 15밖에 없어서 15로 가려는데 이미 갈 수 있는 칸에 있는 칸이라서 넣지는 않고 분기만 더해준다.

이제 더 이상 분기가 없이 자연스럽게 (3, 3): 15 → (3, 4): 10 순서로 방문하면서 분기를 더해주게 되고 최종 적으로 dp[n-1][m-1]이 3으로 총경로가 3개였다는 것을 알 수 있다.

이제 위의 과정을 코드로 구현하면 되는데 보통 이러한 과정에서 이미 갈 수 있는 정점인지 판단할 때 방문한 정점인지 확인하는 bool visit[] 같은 걸 사용하는데 여기선 분기를 저장하는 dp[][]배열을 사용하기 때문에 해당 칸의 분기가 0이면 처음이라는 뜻이고 갈 수 있는 칸에 추가하면 되는 상황이고 0이 아니면 이미 다른 정점에서 해당 정점을 갈 수 있는 칸에 추가를 했다는 뜻이 된다.

실제 코드에 주석을 통해서 설명을 달아 놨다.

#include <iostream>
#include <queue>
#include <tuple>

using namespace std;

int n, m;
// 배열의 크기는 n, m의 최댓값으로 설정하면 됨
int board[500][500];
int dp[500][500];

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

// 갈 수 있는 칸을 저장해서 가장 큰 값을 뽑아줄 우선순위 큐
priority_queue<tuple<int, int, int>> pq;

int main()
{
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
      cin >> board[i][j];
  }
    
  // (0, 0)의 기본 분기는 1이고 우선순위 큐(갈 수 있는 칸)에 넣어주자.
  dp[0][0] = 1;
  pq.push({board[0][0], 0, 0});
    
  int w, x, y;
  int nx, ny;
  while (!pq.empty())
  {
    // w가 가장 큰 좌표가 선택된다.
    tie(w, x, y) = pq.top();
    pq.pop();
        
    // 상하좌우 4칸을 확인
    for (int i = 0; i < 4; i++)
    {
      nx = x + dx[i];
      ny = y + dy[i];
            
      // n x m 배열의 범위를 넘는지 확인
      if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            
      // 지금 높이보다 높으면 갈 수 없다.
      if (board[nx][ny] >= board[x][y]) continue;
            
      // dp[][] == 0은 갈 수 있는 칸에 해당 (nx, ny)가 아직 없다는 의미이다. 이런 경우에만 추가
      if (dp[nx][ny] == 0)
        pq.push({board[nx][ny], nx, ny});
                
      // dp[][]배열을 더해주는 식으로 분기를 누적해 나아간다.
      dp[nx][ny] += dp[x][y];
    }
  }
  cout << dp[n-1][m-1];

  return 0;
}

Complexity

모든 정점이 한 번 이상 우선순위 큐에 삽입되고 삭제되기 때문에 $O(MNlogMN)$정도로 볼 수 있다.

물론 우선순위 큐의 크기가 절대 MN가 될 수 없기 때문에 실제로는 더 적은 시간 복잡도를 갖는다.