[백준 20926] 얼음미로

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

20926번: 얼음 미로

#include <cstdio>
#include <queue>
#include <cstring>
int R, C;
char in[500 + 2][500 + 2];
int board[500 + 2][500 + 2];
int tx, ty;
int ex, ey;

struct _st
{
	int x, y;
	int time;
};

struct COMP
{
	bool operator()(const _st &a, const _st &b)
	{
		return a.time > b.time;
	}
};
std::priority_queue<_st, std::vector<_st>, COMP> PQ;
int visited[500 + 2][500 + 2];
int ans = 0x7fffffff;


void input()
{
	scanf("%d %d", &C, &R);
	for (int i = 0; i < R; i++) {
		scanf("%s", &in[i]);
		for (int j = 0; j < C; j++) {
			if (in[i][j] >= '0' && in[i][j] <= '9') board[i][j] = in[i][j] - '0';
			else if (in[i][j] == 'T') {
				tx = i, ty = j;
				board[i][j] = 0;
			}
			else if (in[i][j] == 'E') {
				ex = i, ey = j;
				board[i][j] = 0;
			}
			else if (in[i][j] == 'R') board[i][j] = -1;
			else if (in[i][j] == 'H') board[i][j] = -2;
		}
	}
}




int simulation()
{

	// dir
	int dir_x[4] = { 0, 0, 1, -1 };
	int dir_y[4] = { 1, -1, 0, 0 };


	// init
	PQ = {};
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			visited[i][j] = 0x7fffffff;
		}
	}

	PQ.push({ tx, ty, 0 });
	visited[tx][ty] = 0;
	

	while (!PQ.empty()) {
		_st data = PQ.top();
		PQ.pop();

		if (data.x == ex && data.y == ey) return data.time;

		for (int p = 0; p < 4; p++) {
			int nx = data.x;
			int ny = data.y;
			bool alive = true;
			int tmp_total = data.time;

			while (1) {
				// 영역 밖
				if (nx + dir_x[p] < 0 || nx + dir_x[p] > R - 1 || ny + dir_y[p] < 0 || ny + dir_y[p] > C - 1) {
					alive = false;
					break;
				}
				// 돌 만남 
				if (board[nx + dir_x[p]][ny + dir_y[p]] == -1) break;

				nx += dir_x[p];
				ny += dir_y[p];
				// 홀만남 
				if (board[nx][ny] == -2) break;
				// 탈출구만남 
				if (nx == ex && ny == ey) break;
				tmp_total += board[nx][ny];
			}
			if (alive == false) continue;
			if (board[nx][ny] == -2) continue;
			if (visited[nx][ny] <= tmp_total) continue;
			visited[nx][ny] = tmp_total;
			PQ.push({ nx ,ny, tmp_total });
		}
	}
	return -1;
}



int main()
{
	input();
	int ans = simulation();
	printf("%d\n", ans);
	//debug();
	return 0;
}

1. 각 칸마다 미끌시간이 다르므로 우선순위 큐 사용한다. 

2. PQ에서 pop된 좌표를 가지고 멈출 때 까지 while문을 돌려본다. 

3. 영역 밖으로 나가서 죽었다면 더이상 상태발전을 진행하지 않는다. 

4. 돌을 만나면 그 전 좌표에서 멈춰야 한다. 

5. 홀을 만나면 해당 좌표에서 더이상 상태발전을 진행하지 않는다. 

6. (3, 4, 5)번이 아니라면 해당 좌표까지 오는데 걸린 미끌시간과 기존 방문배열에 저장된 시간을 비교하여 더 작은 것을 채택한다. 

7. 우선순위 큐를 사용했기 때문에, 거리가 작은 것이 우선적으로 채택된다. 따라서 PQ에서 pop된 데이터가 (ex, ey)이면 바로 리턴한다.