[G4] 백준 12786번 INHA SUIT C++ 다익스트라

리뷰

 

https://www.acmicpc.net/problem/12786

풀이 방향성은 잘 생각했으나 인덱스 매핑에 살짝 아쉬움이 있었던 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 나무의 개수를 저장할 변수
• k : T기능의 최대 사용 횟수를 저장할 변수
• Pos : 현재 통과해야할 나무 인덱스, 현재 높이, T기능 사용횟수를 정의할 구조체, T기능 사용 횟수를 기반으로 오름차순 정렬한다.
• hole : 각 나무의 통과 가능한 구멍의 위치를 저장할 벡터 배열

 

함수

1. dijkstra

int dijkstra() {
	priority_queue<Pos> pq;
	pq.push({ 0, 1, 0 });
	vector<vector<int>> dist(n + 1, vector<int>(21, 2e9));
	dist[0][1] = 0;
	
	while (!pq.empty()) {
		auto [cx, cy, ct] = pq.top(); pq.pop();

		if (cx == n) continue;
		if (dist[cx][cy] < ct) continue;

		for (int ny : hole[cx]) {
			if (cy == ny && dist[cx + 1][ny] > ct) {
				dist[cx + 1][ny] = ct;
				pq.push({ cx + 1, ny, ct });
			}

			if (cy + 1 == ny && dist[cx + 1][ny] > ct) {
				dist[cx + 1][ny] = ct;
				pq.push({ cx + 1, ny, ct });
			}

			if (cy - 1 == ny && dist[cx + 1][ny] > ct) {
				dist[cx + 1][ny] = ct;
				pq.push({ cx + 1, ny, ct });
			}

			if ((cy * 2 > 20 ? 20 : cy * 2) == ny && dist[cx + 1][ny] > ct) {
				dist[cx + 1][ny] = ct;
				pq.push({ cx + 1, ny, ct });
			}

			if (ct < k && dist[cx + 1][ny] > ct + 1) {
				dist[cx + 1][ny] = ct + 1;
				pq.push({ cx + 1, ny, ct + 1 });
			}
		}
	}

	int mn = 2e9;
	for (int i = 1; i < 21; ++i) {
		mn = min(mn, dist[n][i]);
	}
	return mn;
}

 

T기능을 최소한으로 사용해 마지막 나무를 통과할 수 있는지 여부를 확인하기 위한 함수

 

 

문제풀이

1. n, k값을 입력 받고, n개의 나무 구멍의 개수를 변수 m에 입력 받는다.
2. m개의 구멍의 높이를 입력 받고, hole을 초기화한다.
3. 변수 ans에 dijkstra함수를 호출 후 반환받은 값을 저장한다.
4. Pos타입의 우선순위 큐 pq를 초기화 하고, 초기값 {0, 1, 0}을 push한다.
5. 2차원 정수 벡터 dist를 n+1*21크기로, 초기값은 매우 큰 값으로 초기화한다.
6. dist[0][1]을 0으로 저장하여 초기 정보를 저장해준다.
7. pq가 빌때까지 while루프를 수행하고, 변수 cx, cy, ct에 pq의 top요소를 파싱한다.
8. 첫 번째 기저 조건으로 cx가 n에 도달한 경우 더 이상 탐색할 필요가 없으므로 continue처리한다.
9. 두 번째 기저 조건으로 dist[cx][cy]가 ct보다 작을 경우 더 좋은 조건이 있는 것이므로 continue처리한다.
10. hole[cx]를 순회하며 각 빈 구멍의 높이를 변수 ny에 저장한다.
11. O, A, B, C기능을 통해 구멍을 통과할 수 있다면 dist[cx+1][ny]에 ct를 저장하고, 다음 상태를 pq에 삽입한다.
12. T기능을 k번 보다 적게 사용하였고, 더 좋은 조건으로 구멍을 통과할 수 있다면 dist[cx+1][ny]에 ct+1을 저장하고, 다음 상태를 pq에 삽입한다.
13. 변수 mn을 dist의 초기값으로 저장하고, 마지막 나무의 각 높이에 저장된 최소값으로 mn을 갱신한다.
14. 최종적으로 mn에 저장된 값을 반환한다.
15. ans에 저장된 값이 mn의 초기값이라면 -1을, 아니라면 ans에 저장된 값을 출력한다.

 

트러블 슈팅

1. hold을 0-based-indexing으로 설정하였으므로 dist를 n크기로 초기화하였다가 WA를 받았다.
2. dist를 n+1크기로 초기화하고, 저장된 값의 최소값을 반환하여 AC를 받았다.

 

참고 사항

1. B기능 사용 시 만약 현재 높이가 10m 이상이라면 항상 20m로 이동한다.
2. 모든 나무의 높이가 20m이므로 그 이상은 탐색할 필요가 없다.
3. T기능의 사용 횟수가 k번을 넘어섰을 경우 탐색할 필요가 없다.

 

정답 코드

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

const int N = 100;
int n, k;
struct Pos {
	int x, y, t;
	bool operator<(const Pos& other) const {
		return t > other.t;
	}
};
vector<int> hole[N];

int dijkstra() {
	priority_queue<Pos> pq;
	pq.push({ 0, 1, 0 });
	vector<vector<int>> dist(n + 1, vector<int>(21, 2e9));
	dist[0][1] = 0;
	
	while (!pq.empty()) {
		auto [cx, cy, ct] = pq.top(); pq.pop();

		if (cx == n) continue;
		if (dist[cx][cy] < ct) continue;

		for (int ny : hole[cx]) {
			if (cy == ny && dist[cx + 1][ny] > ct) {
				dist[cx + 1][ny] = ct;
				pq.push({ cx + 1, ny, ct });
			}

			if (cy + 1 == ny && dist[cx + 1][ny] > ct) {
				dist[cx + 1][ny] = ct;
				pq.push({ cx + 1, ny, ct });
			}

			if (cy - 1 == ny && dist[cx + 1][ny] > ct) {
				dist[cx + 1][ny] = ct;
				pq.push({ cx + 1, ny, ct });
			}

			if ((cy * 2 > 20 ? 20 : cy * 2) == ny && dist[cx + 1][ny] > ct) {
				dist[cx + 1][ny] = ct;
				pq.push({ cx + 1, ny, ct });
			}

			if (ct < k && dist[cx + 1][ny] > ct + 1) {
				dist[cx + 1][ny] = ct + 1;
				pq.push({ cx + 1, ny, ct + 1 });
			}
		}
	}

	int mn = 2e9;
	for (int i = 1; i < 21; ++i) {
		mn = min(mn, dist[n][i]);
	}
	return mn;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k;
	for (int i = 0; i < n; ++i) {
		int m; cin >> m;

		while (m--) {
			int h; cin >> h;
			hole[i].push_back(h);
		}
	}

	int ans = dijkstra();
	cout << (ans == 2e9 ? -1 : ans);
}