BOJ - 11909번 배열 탈출 문제, Dijkstra 이용한 풀이

이번에 풀이한 문제는 백준 11909번 배열 탈출 문제입니다. 기본적인 다익스트라(dijkstra) 알고리즘을 이용해서 쉽게 풀이할 수 있었습니다.

 

문제 링크는 다음과 같습니다.

11909번: 배열 탈출

---

문제 설명

 

상수는 2차원 배열 A[1..n][1..n] (n≥2, n은 자연수)을 가지고 있습니다. 이 배열의 각 원소는 1 이상 222 이하의 정수입니다.

배열을 가지고 놀던 상수를 본 승현이는, 질투심이 불타올라 상수를 A[1][1]에 가둬 버렸습니다! 최소한의 양심이 있던 승현이는 A[n][n]에 출구를 만들어 놓고 이 사실을 상수에게 알려줬습니다.

출처: BOJ

[그림 1] n=4라면 상수는 A[1,1]에 있고, 출구는 A[4][4]에 있습니다.

 

상수는 가능한 한 빨리 출구인 A[n][n]에 도달하고자 합니다. 상수가 A[i][j]에 있다고 가정했을 때, 상수는 최단 경로로 이동하기 위해 아래와 같은 조건을 만족하며 이동합니다.

1. 1≤i,j<n이라면, 상수는 A[i][j+1] 또는 A[i+1][j]로만 건너갑니다.
2. i=n,1≤j<n이라면, A[i][j+1]로만 건너갑니다.
3. 1≤i<n,j=n이라면 A[i+1][j]로만 건너갑니다.
4. i=j=n인 경우 바로 출구로 갑니다.

출처: BOJ

[그림 2] n=5라고 가정합시다. (ㄱ)는 1번 조건을 만족하고, (ㄴ)는 2번 조건을 만족하며, (ㄷ)는 3번 조건을 만족합니다.

 

그러나 건너갈 때에도 제약이 따릅니다. 상수가 A[a][b]에서 A[c][d]로 건너가려면 A[a][b]>A[c][d]를 만족해야 합니다. 상수는 왜인지 이런 조건을 만족하면서 이동할 수 없을 것 같았습니다. 다행히도, 승현이가 상수를 배열에 가둬버리기 전에, 상수는 배열의 각 원소에 버튼을 만들어 놓아서, 이 버튼을 누르면 해당 원소의 값이 1 증가하도록 했습니다. (물론 상수는 자신이 위치해 있는 원소의 버튼만 누를 수 있습니다.) 이 버튼 덕분에, 상수는 항상 배열을 탈출할 수 있습니다!

출처: BOJ

[그림 3] n=2라고 가정합시다. A[1][1]=5>A[1][2]=2이므로, 상수는 A[1][1]에서 A[1][2]로 건너갈 수 있습니다. 상수가 A[1][1]에서 A[2][1]로 건너가려면, A[1][1]에 있는 버튼을 두 번 눌러 A[1][1]의 값을 7로 만들면 됩니다.

 

하지만 버튼을 한 번 누르는 데에는 1원의 비용이 듭니다. 상수는 돈을 가능한 한 적게 들이면서 배열을 탈출하고자 합니다. 상수를 도와주세요.

 

입력

첫 번째 줄에 n이 주어집니다. (n ≤ 2,222)

다음에 n개 줄이 주어집니다. 이 중 i(1≤i≤n)번째 줄에는 n개의 수 A[i][1],A[i][2],⋯,A[i][n−1],A[i][n]이 공백을 사이로 두고 차례대로 주어집니다.

 

출력

첫 번째 줄에 상수가 배열을 탈출하기 위해 들여야 할 최소 비용(원 단위)을 출력합니다.

 

예제 입력및 출력

입력:
4
5 2 4 3
6 5 1 2
3 4 5 3
7 4 3 1

출력:
3
============
입력:
5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

출력:
8

(1, 1)을 시작점으로 하고, (n, n)을 종착점으로 하는 경로에 대해서 그래프를 탐색하며 최단 경로를 찾는 문제이기 때문에, 다익스트라 알고리즘을 이용해서 풀어야겠다는 생각을 할 수 있었습니다.

 

Dynamic programming(동적 계획법) 방식으로 각 위치에서 소모한 최소 금액을 기록하면서 도착 지점까지 가는데 드는 최소 금액을 구하는 방식으로 구현했습니다.

 

앞서 문제 설명에서 알 수 있는 바와 같이 현재 칸의 값이 다음으로 이동할 칸의 값보다 큰 경우에는 추가적인 지불 없이 이동할 수 있지만, 현재 칸의 값이 작은 경우에는 다음 칸보다 값이 커질 때까지 돈을 지불해야 하기 때문에, 이를 고려해야 합니다. (이 부분은 "다음 칸의 값 - 현재 칸의 값 + 1" 만큼의 비용을 지불하면 이동할 수 있도록 구현합니다.)

 

이동할 수 있는 위치는 그래프의 우측 or 하단으로만 이동할 수 있으며, 이동할 수 있는지 여부를 판단하기 위해 inRange라는 함수를 따로 구현해 풀이했습니다.

 

마지막으로 배열의 각 원소 값이 1 ~ 222 범위이고, 배열의 최대 크기가 2222x2222 이므로 발생할 수 있는 최대 값보다 배열을 더 큰 값으로 초기화하기 위해서 (이렇게 해야 다익스트라 방식으로 최소 경로를 구할 수 있기 때문입니다!) 전체 배열을 10000000으로 초기화한 후에 다익스트라를 이용한 그래프 탐색을 진행 했습니다.

---

소스 코드

/*
	Date: 2022/07/22
	Brief:
	Dijkstra
	Reference:
*/
#include <iostream>
#include <queue>
#define MAX 2223
#define INF 10000000

using namespace std;

int arr[MAX][MAX];
int minMoney[MAX][MAX];
int n;

bool inRange(int x, int y) {
	return (1 <= x && x <= n && 1 <= y && y <= n);
}

void initialization() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			minMoney[i][j] = INF;
		}
	}
}

void dijkstra(int x, int y) {
	priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
	pq.push({ 0, {x, y} });

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

	minMoney[x][y] = 0;

	while (!pq.empty()) {
		int x = pq.top().second.first;
		int y = pq.top().second.second;
		int money = pq.top().first;
		pq.pop();

		for (int i = 0; i < 2; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			int next_money = money;
			if (!inRange(nx, ny))
				continue;
			// 현재 기준 누적 금액 계산
			if (arr[nx][ny] >= arr[x][y]) {
				next_money += (arr[nx][ny] - arr[x][y] + 1);
			}
			// 갱신 안되는 경우 skip
			if (next_money >= minMoney[nx][ny])
				continue;

			minMoney[nx][ny] = next_money;
			pq.push({ next_money, {nx, ny} });
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
		}
	}
	initialization();

	dijkstra(1, 1);

	cout << minMoney[n][n] << "\n";

	return 0;
}

처음에 ios::sync_with_stdio(false); 부분을 작성하지 않아서 시간 초과가 나는 부분이 있어서 코드 수정 후에 정답 처리를 받을 수 있었습니다.

수정 후 정답처리

// 아래의 코드를 작성해야 입출력에서의 시간을 단축할 수 있습니다.
ios::sync_with_stdio(false);
cin.tie(NULL);

sync_with_stdio(false)를 사용하게 되면, c와 c++ 표준 스트림의 동기화를 끊게 되어, 기존에 c와 c++ 버퍼를 병행해서 사용하던 것을 c++의 버퍼만 사용하게 되어 버퍼의 수가 줄면서, 실행 속도를 빠르게 할 수 있다고 합니다.

(동기화를 끊기 때문에, sync_with_stdio(false)를 사용한 이후에 c의 입출력 문법을 사용하는 경우 에러가 발생합니다!)

 

추가적으로 cin.tie(NULL)은 cin과 cout의 묶음을 풀어주는 작업을 수행한다고 합니다. cout의 경우에는 버퍼에 추가된 이후 출력 명령을 내리거나 버퍼가 가득 찬 경우에만 버퍼를 비우기 때문에, cin과 cout의 묶음을 해제한다고 합니다.

---

References:

https://jaimemin.tistory.com/1521

ios_base::sync_with_stdio(false); cin.tie(null); 구문을 추가해주는 이유