C++로 풀어보는 '상승하는 물에서 수영하기' 문제 – 다익스트라 알고리즘 활용법

문제 설명

N × N 크기의 격자가 하나 있다고 가정해 봅시다. 각 칸 grid[i][j]는 그 지점 (i, j)의 고도(높이)를 나타냅니다. 이제 비가 내리기 시작했으며, 시각 t일 때 모든 위치의 물 깊이는 t라고 합니다. 우리는 한 칸에서 상하좌우로 인접한 다른 칸으로 이동할 수 있는데, 조건은 두 칸의 고도가 각각 t 이하일 때입니다. 또한 무한히 먼 거리도 시간 0에 헤엄쳐 이동할 수 있다고 가정합니다.

출발점은 (0, 0)이며, 목표는 오른쪽 맨 아래 칸인 (N-1, N-1)입니다. 이 목적지에 도달할 수 있는 최소 시간을 구하는 것이 과제입니다.

예를 들어 입력이 다음과 같다면:

파란색으로 표시된 경로가 최적 경로이며, 따라서 정답은 16이 됩니다.

접근 방법: 다익스트라 알고리즘 응용

이 문제는 우선순위 큐(priority queue)를 활용한 다익스트라(Dijkstra) 스타일의 탐색으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 "지금까지 지나온 칸들의 최대 고도"를 경로의 비용으로 간주하고, 그 비용이 가장 작은 경로부터 먼저 확장하는 것입니다. 이렇게 하면 목적지에 처음 도달하는 순간의 값이 곧 최소 시간이 됩니다.

구체적인 알고리즘 단계는 다음과 같습니다.

• time(경로상 최대 고도), x, y 세 값을 담는 구조체 Data를 정의합니다.
• 4방향 이동 배열 dir(크기 4×2) := {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}을 선언합니다.
• n := 격자의 행 개수, m := 격자의 열 개수로 설정합니다.
• time이 작은 순으로 정렬되는 우선순위 큐 q를 정의합니다.
• n × m 크기의 2차원 방문 배열 visited를 만들고 0으로 초기화합니다.
• visited[0][0] := 1로 표시합니다.
• q에 Data(grid[0][0], 0, 0)을 삽입합니다.
• q가 빌 때까지 다음을 반복합니다:
  • q의 최상단 노드를 꺼내고 제거합니다.
  • time := node.time, x := node.x, y := node.y로 설정합니다.
  • x == n-1 && y == m-1이라면 time을 반환합니다.
  • i = 0부터 3까지 반복합니다:
    • nx := dir[i][0] + x, ny := dir[i][1] + y로 계산합니다.
    • nx, ny가 격자 범위 안에 있고 visited[nx][ny] == 0이라면:
      • visited[nx][ny] := 1로 방문 처리합니다.
      • q에 Data(max(grid[nx][ny], time), nx, ny)를 삽입합니다.
• 반복문이 종료되면 -1을 반환합니다(목적지에 도달할 수 없는 경우).

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
struct Data{
    int time, x, y;
    Data(int a, int b, int y){
        time = a;
        x = b;
        this->y = y;
    }
};
struct Comparator{
    bool operator()(Data a, Data b){
        return !(a.time < b.time);
    }
};
int dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        priority_queue <Data, vector <Data>, Comparator> q;
        vector < vector <int> > visited(n, vector <int>(m, 0));
        visited[0][0] = 1;
        q.push(Data(grid[0][0], 0, 0));
        while(!q.empty()){
            Data node = q.top();
            q.pop();
            int time = node.time;
            int x = node.x;
            int y = node.y;
            if(x == n - 1 && y == m - 1)return time;
            for(int i = 0; i < 4; i++){
                int nx = dir[i][0] + x;
                int ny = dir[i][1] + y;
                if(nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]){
                    visited[nx][ny] = 1;
                    q.push(Data(max(grid[nx][ny], time), nx, ny));
                }
            }
        }
        return -1;
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{0,1,2,3,4},{24,23,22,21,5},{12,13,15,15,16},{11,17,18,19,20}, {10,9,8,7,6}};
    cout << (ob.swimInWater(v));
}

입력

{{0,1,2,3,4},{24,23,22,21,5},{12,13,15,15,16},{11,17,18,19,20},{10,9,8,7,6}}

출력

16

복잡도 분석

시간 복잡도: O(N² log N) — 모든 칸이 우선순위 큐에 한 번씩 삽입·삭제되기 때문입니다.
공간 복잡도: O(N²) — 방문 배열과 우선순위 큐 저장 공간이 필요합니다.