[G5] 백준 17836번 공주님을 구해라! C++ 다익스트라

리뷰

 

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

(0, 0) 좌표에서 (N - 1, M - 1) 좌표까지 가는 최단거리를 구하는 문제

단, 중간에 검을 획득할 경우 모든 벽을 부실 수 있다는 조건이 추가되어 있다.

 

 

전역 변수

• N : 맵의 세로 길이를 저장할 변수
• M : 맵의 가로 길이를 저장할 변수
• T : 제한 시간을 저장할 변수
• lst : 맵 정보를 입력 받아 저장할 배열
• dx, dy : 4방향 탐색을 위한 방향 배열
• Pos : 현재 위치x, y와 시간 t, 검 획득 여부 k를 정의하기 위한 구조체, t를 기준으로 오름차순 정렬한다.

 

함수

1. floodfill

int floodfill()

 

플러드 필을 통해 2차원 맵에서 퍼져나가며 다익스트라로 최단 경로를 찾기 위한 함수

1. Pos타입의 우선순위 큐 pq를 초기화 하고, 초깃값 {0, 0, 0, 0}을 push해준다.
2. N * M * 2크기의 3차원 정수형 벡터 dist를 초기화 하고 매우 큰 값을 넣어준다.
3. 초기 위치와 검을 먹지 않은 경우인 dist[0][0][0]을 0으로 초기화 해준다.
4. pq가 빌 때 까지 while루프를 수행하고, 매 루프마다 요소를 한개씩 꺼내어 준다.
5. 첫 번째 기저 조건으로 (N - 1, M - 1)에 도착한 경우 ct를 리턴해 준다.
6. 두 번째 기저 조건으로 현재 시간 ct가 제한 시간 T보다 클 경우 continue 처리해 준다.
7. 4방향 탐색을 진행하고 다음 위치로 이동해 준다.
8. nk가 0인 경우 즉, 키를 갖고 있지 않을 경우 벽을 만났다면 continue처리해 준다.
9. 맵 상에서 2를 만났다면 검을 획득하고 nk를 1로 변경해 준다.
10. 이동할 위치와 nk차원의 dist가 nt(현재시간 + 1)보다 크다면 값을 갱신해 준다.
11. pq에 이동한 위치, 증가한 시간, 검 획득 여부를 push해준다.
12. nk가 1인 경우 즉, 키를 갖고 있는 경우 이동할 위치의 값이 nt보다 클 경우 갱신하고 pq에 push해준다.
13. while루프가 종료될 때 까지 첫 번째 기저 조건에 도달하지 못한 경우 -1을 리턴해 준다.

 

2. print

void print(int x, int y, int t, int k)

 

디버깅용 함수

 

문제풀이

1. N, M, T 값을 입력 받고, N * M크기의 맵 정보를 입력 받아준다.
2. floodfill 함수를 통해 리턴받은 값을 변수 result에 저장해 준다.
3. result가 -1이라면 Fail을, 아니라면 result에 저장된 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 예제가 잘 나오지 않는다면 디버깅을 통해 시뮬레이션을 직접 돌려보자
• 나 처럼 dist의 초기값을 0으로 하던가 !pq.empty()가 아닌 pq.empty()로 작성한 실수를 바로 찾을 수 있다.

 

정답 코드

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

int N, M, T;
int lst[100][100];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };

struct Pos {
	int x, y, t;
	bool k;
	bool operator<(const Pos& other) const {
		return t > other.t;
	}
};

void print(int x, int y, int t, int k) {
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			if (x == i && y == j) cout << 9 << " ";
			else cout << lst[i][j] << " ";
		}
		cout << "\n";
	}
	cout << t << " " << k << "\n";
}

int floodfill() {
	priority_queue<Pos> pq;
	pq.push({ 0, 0, 0, 0 });
	vector<vector<vector<int>>> dist(N, vector<vector<int>>(M, vector<int>(2, 2e9)));
	dist[0][0][0] = 0;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.x, cy = pos.y, ct = pos.t;
		bool ck = pos.k;
		//print(cx, cy, ct, ck);
		if (cx == N - 1 && cy == M - 1) return ct;
		if (ct > T) continue;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i], nt = ct + 1;
			bool nk = ck;
			if (0 <= nx && nx < N && 0 <= ny && ny < M) {
				if (!nk) {
					if (lst[nx][ny] == 1) continue;
					else if (lst[nx][ny] == 2) nk = 1;
					if (dist[nx][ny][nk] > nt) {
						dist[nx][ny][nk] = nt;
						pq.push({ nx, ny, nt, nk });
					}
				}
				else {
					if (dist[nx][ny][nk] > nt) {
						dist[nx][ny][nk] = nt;
						pq.push({ nx, ny, nt, nk });
					}
				}
			}
		}
	}
	return -1;
}

int main() {
	cin >> N >> M >> T;
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < M; ++j)
			cin >> lst[i][j];

	int result = floodfill();
	if (result == -1) cout << "Fail";
	else cout << result;
}