백준 22255 호석사우로스 c++ (다익스트라)

문제 출처 : https://www.acmicpc.net/problem/22255

22255번: 호석사우루스

문제

음머... 미련한 소인 호석사우루스는 융통성 따위 일절 가지지 않는다. 자신의 철칙에 맞게 우직하게 미궁을 탈출하려고 한다. 미궁은 N행 M열의 격자로 이루어져 있고 각 칸마다 입장하는 순간 받는 충격량이 있다. 같은 방을 여러 번 들어가면, 들어갈 때마다 같은 충격량을 받게 된다. 당연히 똑똑한 소라면 최소의 충격을 받으면서 미궁을 탈출하던가, 애초에 미궁에 안 빠지도록 머리를 썼겠지만, 호석사우루스는 그런 거 없다!

그의 철칙은, 이동 방식에 있다. 매 이동 시 마다 움직일 수 있는 방향이 다르다.

•  3K 번째 이동 시에는 상, 하, 좌, 우로 인접한 곳 중 한 칸으로 이동할 수 있다.
•  3K+1 번째 이동 시에는 상, 하로 인접한 곳 중 한 칸으로 이동할 수 있다.
•  3K+2 번째 이동 시에는 좌, 우로 인접한 곳 중 한 칸으로 이동할 수 있다.
• 만약 이동하려는 곳에 벽이 있으면 이동할 수 없다.
• 최초의 이동은 1번째 이동이고, 이후에 2번째, 3번째 이동이다.

자신의 철칙을 지키되, 아픈 건 싫어하는 호석사우루스를 도와서 탈출구까지의 최소 충격량을 구해주자!

입력

첫 번째 줄에 격자의 크기 N, M이 주어진다.

두 번째 줄에 시작 지점과 도착 지점의 정보인 Sx, Sy, Ex, Ey 가 공백으로 구분되어 주어진다. 시작 지점이 Sx행 Sy열이며 도착 지점이 Ex행 Ey열임을 의미한다. 시작 지점과 도착 지점은 항상 다르다.

세 번째 줄부터 N개 줄에 걸쳐서 지도의 정보가 주어진다. 각 줄마다 M개의 정수가 주어진다. i+2번 줄의 j번째 숫자는 i행 j열에 위치한 격자의 충격량을 의미한다. 만약 충격량 정보가 −1이라면 해당 격자는 벽임을 의미한다.

시작점과 도착점의 충격량은 0 임이 보장된다.

출력

첫 번째 줄에 호석사우루스가 탈출하는 과정에서 받는 최소 충격량을 출력한다. 만약 탈출하지 못한다면 −1을 출력한다.

제한

• 1 ≤ N, M ≤ 100
• 1 ≤ Sx,Ex ≤ N 
• 1 ≤ Sy,Ey ≤ M 
• -1 ≤ 각 칸의 충격량 ≤ 300

알고리즘 분류

• 그래프 이론
• 다익스트라

풀이

움머~

호석님 문제 너무 좋다.

그래프 탐색 문제이다.

이동 방향은 3개의 패턴이 있으며,

첫 번째 이동엔 상하,

두 번째 이동엔 좌우,

세 번째 이동엔 상하좌우로 이동할 수 있고, 네 번째부터 다시 첫 번째 이동 패턴이 반복된다.

이는, 현재 이동 횟수를 3으로 나눈 값으로 첫 번째, 두 번째, 세 번째 이동을 파악할 수 있고,

미리 3개 패턴의 방향을 저장해놓음으로써 구현할 수 있다.

 

다음으로는, 그래프를 어떻게 탐색할지 방식을 정해야 한다.

문제의 조건을 보면, 어떠한 좌표 r,c에 있을때, 현재 몇 번째 이동인지에 따라서 갈 수 있는 칸이 달라진다.

따라서 우리는 단순히 한 번 방문했던 노드는 재방문하지 않는 것이 아니라,

같은 이동 방향을 가진 상태로 한 번 방문했던 노드는 재 방문할 필요가 없어 보인다.

하지만 우리는 목적지까지의 최소 거리가 아닌, 그래프의 칸들을 방문하면서 누적되는 최소 충격량을 구해야 하기 때문에, 해당 칸에 같은 이동 방향을 가진 상태로 이미 방문했더라도, 더 낮은 충격량으로 칸에 도착할 수 있다면, 해당 칸을 탐색해야 한다.

즉, 해당 칸의 방문 여부가 아닌, 해당 칸을 도착했을 때 최소 충격량을 기준으로 탐색하고, 충격량은 모두 같은 값이 아니기 때문에, 다익스트라 알고리즘을 이용해야 한다.

 

이제 위에서 정리한 풀이로 코드를 구현하면 되고, visited dp는 visited[3][n][m]으로 선언하여 현재 칸의 3개의 이동 패턴에 대해 최소 충격량을 저장해 주자.

 

코드

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

//1<=n,m<=100
//-1<=충격량<=300
int n, m;
int sR, sC, eR, eC;
int graph[101][101];
int visited[3][101][101];
pair<int,int> dir[3][4];
struct nodeInfo {
	int  r, c, cnt,damage;
};

struct cmp {
	bool operator()(nodeInfo &a, nodeInfo &b) {
		return a.damage > b.damage;
	}
};

bool isInside(int r,int c) {
	if (r < 1 || r > n || c < 1 || c > m) return false;
	return true;
}

int dijkstra() {
	priority_queue<nodeInfo,vector<nodeInfo>,cmp> pq;
	pq.push({ sR,sC,1,0 });
	int answer = 987654321;
	while (!pq.empty()) {
		int r = pq.top().r;
		int c = pq.top().c;
		int cnt = pq.top().cnt;
		int damage = pq.top().damage;
		pq.pop();
		
		if (visited[cnt % 3][r][c] < damage) continue;
		if (r == eR && c == eC) {
			answer = min(answer, damage);
			break;
		}
		int range = 0;
		if (cnt % 3 == 0) {
			range = 4;
		}
		else {
			range = 2;
		}
;		for (int i = 0; i < range; i++) {
			int nR = r + dir[cnt % 3][i].first;
			int nC = c + dir[cnt % 3][i].second;
			if (!isInside(nR, nC))continue;
			if (graph[nR][nC] == -1) continue;
			if (visited[(cnt+1) % 3][nR][nC] > damage + graph[nR][nC]) {
				visited[(cnt+1) % 3][nR][nC] = damage + graph[nR][nC];
				pq.push({ nR,nC,cnt + 1,damage + graph[nR][nC] });
			}
		}

	}
	if (answer == 987654321) {
		return -1;
	}
	return answer;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	cin >> sR >> sC >> eR >> eC;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> graph[i][j];
		}
	}
	dir[0][0] = { 0,1 };
	dir[0][1] = { 1,0 };
	dir[0][2] = { 0,-1 };
	dir[0][3] = { -1,0 };
	dir[1][0] = { 1 , 0 };
	dir[1][1] = { -1, 0 };
	dir[2][0] = { 0,1 };
	dir[2][1] = { 0,-1 };
	for (int i = 0; i < 3; i++) {
		for (int j = 1; j <= 100; j++) {
			for (int k = 1; k <= 100; k++) {
				visited[i][j][k] = 987654321;
			}
		}
	}
	cout << dijkstra();

	return 0;
}