[백준 22255] 호석사우루스

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

22255번: 호석사우루스

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
int R, C;
int sx, sy;
int ex, ey;
int board[100 + 2][100 + 2];


struct _st
{
	int x, y;
	int move;
	int attack;
};

struct COMP
{
	bool operator()(const _st &a, const _st &b)
	{
		return a.attack > b.attack;
	}
};

std::priority_queue<_st, std::vector<_st>, COMP> PQ;
int visited[100 + 2][100 + 2][3];	// 어떤 방향으로 이동해 왔는지 
									// 같은 방향으로 온적이 있는데 충격량이 더 작다면 굳이 이동할 필요 없다


void input()
{
	scanf("%d %d", &R, &C);
	scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {
			scanf("%d", &board[r][c]);
		}
	}
}


int BFS()
{
	// dir
	// 상 하 좌 우
	int dir_x[4] = { -1, 1, 0, 0 };
	int dir_y[4] = { 0, 0, -1, 1 };

	// init
	PQ = {};
	for (int r = 1; r <= 100; r++) {
		for (int c = 1; c <= 100; c++) {
			visited[r][c][0] = 0x7fffffff;
			visited[r][c][1] = 0x7fffffff;
			visited[r][c][2] = 0x7fffffff;
		}
	}

	PQ.push({ sx, sy, 0, 0 });

	while (!PQ.empty()) {
		_st data = PQ.top();
		//printf("(%d %d) %d >>%d\n", PQ.top());
		PQ.pop();

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

		int nmove = data.move + 1;
		int nattack = -1;

		if (nmove % 3 == 0) {
			for (int p = 0; p < 4; p++) {
				int nx = data.x + dir_x[p];
				int ny = data.y + dir_y[p];

				if (nx < 1 || nx > R || ny < 1 || ny > C) continue;
				if (board[nx][ny] == -1) continue;
				nattack = data.attack + board[nx][ny];
				if (visited[nx][ny][0] <= nattack) continue;
				PQ.push({ nx, ny, nmove, nattack });
				visited[nx][ny][0] = nattack;
			}
		}
		else if (nmove % 3 == 1) {
			for (int p = 0; p < 2; p++) {
				int nx = data.x + dir_x[p];
				int ny = data.y + dir_y[p];

				if (nx < 1 || nx > R || ny < 1 || ny > C ) continue;
				if (board[nx][ny] == -1) continue;
				nattack = data.attack + board[nx][ny];
				if (visited[nx][ny][1] <= nattack) continue;
				PQ.push({ nx, ny, nmove, nattack });
				visited[nx][ny][1] = nattack;
			}
		}
		else if (nmove % 3 == 2) {
			for (int p = 2; p < 4; p++) {
				int nx = data.x + dir_x[p];
				int ny = data.y + dir_y[p];

				if (nx < 1 || nx > R || ny < 1 || ny > C ) continue;
				if (board[nx][ny] == -1) continue;
				nattack = data.attack + board[nx][ny];
				if (visited[nx][ny][2] <= nattack) continue;
				PQ.push({ nx, ny, nmove, nattack });
				visited[nx][ny][2] = nattack;
			}
		}
	}
	return -1;
}


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

상태 정의를 하는데 있어서, "어떤 방식으로 해당 칸에 도달하는지" 와 "해당 칸에 도달하기 까지 누적된 충격량"이 중요했다. 

따라서 0 / 1 / 2 (3가지) 방식으로 특정 칸에 도달할 수 있으므로 3차원 방문배열을 만들고, 충격량을 값으로 저장해준다. 

도착지점인 (ex, ey)까지 가는 최단 거리가 아니라 최소 충격량이므로, 우선순위 큐에서 원소를 pop하는 기준은 "충격량이 작은 순"이다. 

그리고 제발 초기화 주의.... 인덱스 (1 ~ N)인지 (0 ~ N - 1)인지 생각하면서 풀자..