백준 9376 탈옥

백준 9376←클릭

아이디어

• 죄수 2명과 상근이의 위치를 기준으로 다익스트라를 적용하여 지도의 각 위치까지의 최소 거리를 모두 구한다.
  
  
• 지도의 특정 위치에서 세 최소 거리의 합은 해당 위치까지 상근이와 죄수 2명이 최소 거리로 이동했을 때 드는 비용이다.
  
  
• 특정 위치에 문이 있을 경우 2를 빼주는데 이는 단순이 합을 구하게 되면 해당 위치에서 문을 3번 열기 때문이다.
  
  
• 가장 비용이 적게 드는 값을 찾는다.

변수 설정

• sx1, sy1, sx2, sy2 : 죄수의 위치
• VertexInfo : 노드의 좌표와 시작 지점에서 해당 위치까지 가는데 드는 비용을 저장하는 구조체
• dij[i][j][k]:다익스트라 거리 저장 3차원 배열, i는 사람 정보, j, k는 좌표 정보
• pq: 다익스트라 구현을 위한 우선순위 큐

예시

문제의 2번째 예시를 사용해보자.

상근이의 위치를 밖으로 설정하기 위해 맵 주변을 .으로 감싸주고 상근이의 위치를 (0,0)으로 설정한다.

1. 상근이 기준 다익스트라 결과
   

2. 죄수 1 기준 다익스트라 결과
   

3. 죄수 2 기준 다익스트라 결과
   

cost 합:

고로 최소값은 0이다!

코드

github

#define _CRT_SECURE_NO_WARNINGS
#define INF 2100000000
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

char map[102][102];

int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int sx1, sy1, sx2, sy2;
int TC, h, w;
int min_cost;
bool print = false;

int dij[3][102][102];
bool visited[3][102][102];

void setting();
void solution();
void dijkstra(int x, int y, int p);
void cal_cost();
struct VertexInfo {
	int x;
	int y;
	int cost;

	bool operator <(const VertexInfo& v) const{
		return cost > v.cost;
	}
};


int main() {
	//freopen("input/9376_input.txt", "r", stdin);
	
	cin >> TC;
	while (TC--) {
		setting();
		solution();
	}
	return 0;
}

void setting() {
	/* 초기화 */
	sx1 = -1; sx2 = -1; sy1 = -1; sy2 = -1;
	min_cost = 987654321;
	cin >> h >> w;
	if (print) printf("h: %d, w: %d\n", h, w);
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j <= h + 1; j++) {
			for (int k = 0; k <= w + 1; k++) {
				dij[i][j][k] = INF;
				visited[i][j][k] = false;
			}
		}
	}
	for (int i = 0; i <= h + 1; i++) {
		for (int j = 0; j <= w + 1; j++) {
			
			if (i == 0 || i == h + 1 || j == 0 || j == w + 1) {
				map[i][j] = '.';
			}
			else {
				cin >> map[i][j];
				if (map[i][j] == '$') {
					map[i][j] = '.';
					if (sx1 == -1) {
						sx1 = i;
						sy1 = j;
					}
					else {
						sx2 = i;
						sy2 = j;
					}
				}
					
			}
		}
	}
	if (print) {
		for (int i = 0; i <= h + 1; i++) {
			for (int j = 0; j <= w + 1; j++) {
				cout << map[i][j];
			}
			cout << endl;
		}
	}
	
}

void solution() {
	dijkstra(0, 0, 0);
	dijkstra(sx1, sy1, 1);
	dijkstra(sx2, sy2, 2);
	cal_cost();
	cout << min_cost << endl;
}

void dijkstra(int x, int y, int p) {
	if (print)printf("dijkstra(%d, %d, %d)\n", x, y, p);
	priority_queue<VertexInfo> pq; //오름차순으로 해야함
	visited[p][x][y] = true;
	pq.push({ x, y, 0 });
	while (!pq.empty()) {
		int cur_x = pq.top().x;
		int cur_y = pq.top().y;
		int cur_c = pq.top().cost;
		pq.pop();
		if (print)printf("cur_x: %d, cur_y: %d, cur_c: %d\n", cur_x, cur_y, cur_c);
		if (dij[p][cur_x][cur_y] <= cur_c) continue;
		dij[p][cur_x][cur_y] = cur_c;
		for (int i = 0; i < 4; i++) {
			int nx = cur_x + dx[i];
			int ny = cur_y + dy[i];
			if (nx < 0 || nx > h + 1 || ny < 0 || ny > w + 1) continue;
			else {
				if (!visited[p][nx][ny]) { //처음 방문하는 곳 인 경우
					if (map[nx][ny] == '.') {
						if (print)printf("pushed: %d, %d, %d\n", nx, ny, cur_c);
						pq.push({ nx, ny, cur_c });
						visited[p][nx][ny] = true;
					}
					else if (map[nx][ny] == '#') {
						if (print)printf("pushed: %d, %d, %d\n", nx, ny, cur_c + 1);
						pq.push({ nx, ny, cur_c + 1});
						visited[p][nx][ny] = true;
					}
				}
				else { //이미 방문한 적 있는 경우
					if (map[nx][ny] == '.' && dij[p][nx][ny] > cur_c) {
						if (print)printf("(재방문)pushed: %d, %d, %d\n", nx, ny, cur_c);
						pq.push({ nx, ny, cur_c });
					}
					else if (map[nx][ny] == '#' && dij[p][nx][ny] > cur_c + 1) {
						if (print)printf("(재방문)pushed: %d, %d, %d\n", nx, ny, cur_c + 1);
						pq.push({ nx, ny, cur_c + 1 });
					}
				}
			}
		}
	}
	if (print) {
		for (int i = 0; i <= h + 1; i++) {
			for (int j = 0; j <= w + 1; j++) {
				if (dij[p][i][j] == INF) cout << "x";
				else cout << dij[p][i][j];
			}
			cout << endl;
		}
	}	
}
void cal_cost() {
	if (print) cout << "cal_cost" << endl;
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			int c = 0;
			for (int k = 0; k < 3; k++) {
				if (dij[k][i][j] != INF) c += dij[k][i][j]; //오버플로우 조심
				else c = INF;
			}
			if (map[i][j] == '#') c -= 2;
			min_cost = min(min_cost, c);
			if (print) {
				if (c >= INF) cout << "x";
				else cout << c;
			}
		}
		if(print) cout << endl;
	}
}