취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 9911번 문제인 ERP이다.
문제는 아래 링크를 확인하자.

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

주어진 문제에서 차의 상태는 주어진 격자의 좌표 \((x,y)\)와 차가 바라보고 있는 방향 \(d\)를 묶은 순서쌍 \(((x,y),d)\)들로 표현할 수 있다. 이러한 각 상태를 노드로, 한 상태에서 다른 상태로의 변화를 그 때 들어가는 비용을 가중치로 갖는 에지로 생각하면 주어진 문제상황은 가중치 있는 방향그래프에서 최단거리를 구하는 문제로 모델링할 수 있게 된다.

이는 대표적으로 dijkstra 알고리즘을 이용하여 해결할 수 있다.

유턴을 할 수 있는 조건의 구현에 특히 유의하자.

아래는 제출한 소스코드이다.

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

int R, C, sR, sC, sdir, eR, eC;
string board[30];
int dist[30][30][4];

priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;
int dr[4] = {1,0,-1,0};
int dc[4] = {0,-1,0,1};
int cost[4] = {0,5,10,1};

void dijkstra() {
	memset(dist, 0x3f, sizeof(dist));
	dist[sR][sC][sdir] = 0;
	pq.push(make_pair(0, make_pair(sR * 1000 + sC, sdir)));
	while (!pq.empty()) {
		int r = pq.top().second.first / 1000, c = pq.top().second.first % 1000, dir = pq.top().second.second, w = pq.top().first; pq.pop();
		if (dist[r][c][dir] < w) continue;
		int mvtry = 0;
		for (int i = 0; i < 4; i++) {
			if (i == 2) continue;
			int ddir = (dir + i) % 4;
			int rr = r + dr[ddir], cc = c + dc[ddir];
			if (rr < 0 || rr >= R || cc < 0 || cc >= C) continue;
			if (board[rr][cc] != '#') continue;
			mvtry++;
			int ww = dist[r][c][dir] + cost[i];
			if (ww < dist[rr][cc][ddir]) dist[rr][cc][ddir] = ww, pq.push(make_pair(ww, make_pair(rr * 1000 + cc, ddir)));
		}
		if (!mvtry) {
			int i = 2;
			int ddir = (dir + i) % 4;
			int rr = r + dr[ddir], cc = c + dc[ddir];
			if (rr < 0 || rr >= R || cc < 0 || cc >= C) continue;
			if (board[rr][cc] != '#') continue;
			mvtry++;
			int ww = dist[r][c][dir] + cost[i];
			if (ww < dist[rr][cc][ddir]) dist[rr][cc][ddir] = ww, pq.push(make_pair(ww, make_pair(rr * 1000 + cc, ddir)));
		}
	}
}

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

	cin >> R >> C;
	for (int r = 0; r < R; r++) {
		cin >> board[r];
	}

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (board[r][c] == 'F') {
				eR = r, eC = c;
				board[r][c] = '#';
			}
			else if (board[r][c] == 'S') {
				sR = r, sC = c, sdir = 0;
				board[r][c] = '#';
			}
			else if (board[r][c] == 'W') {
				sR = r, sC = c, sdir = 1;
				board[r][c] = '#';
			}
			else if (board[r][c] == 'N') {
				sR = r, sC = c, sdir = 2;
				board[r][c] = '#';
			}
			else if (board[r][c] == 'E') {
				sR = r, sC = c, sdir = 3;
				board[r][c] = '#';
			}
		}
	}

	dijkstra();

	cout << min(min(dist[eR][eC][0], dist[eR][eC][1]), min(dist[eR][eC][2], dist[eR][eC][3]));
}

BOJ Random Defense #11