백준 2645 - 회로배치(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2645

2645번: 회로배치

복잡했던 다익스트라 문제였습니다.

A와 B를 최소 비용으로 이을려고 할 때의 비용을 구하는 문제입니다.

격자판 위에 다른 회로가 있을 수도 있습니다. A와 B를 이을 때, 선이 다른 회로의 위에 있을 경우, K의 비용이 들어가고,
다른 회로가 없을 경우에는 1의 비용이 들어갑니다.

따라서, 처음으로는 다른 회로가 어떻게 있는지를 구하는 것이 중요합니다.
입력에서 (3, 3, 9, 3, 4, 10, 4)로 주어지는데, 이는 3개의 정점이 주어지고 각각 (3, 9) / (3, 4) / (10 ,4) 정점이 주어진다는 의미입니다.
시작점과 끝점이 주어지고, 사이의 정점은 회로가 꺾이는 정점입니다.
즉, (3, 9) -> (3, 4)까지 같은 방향으로 가다가 (10, 4)까지는 다른 방향으로 간다는 의미입니다.

그러니, 회로를 만들 때, 시작점에서 다음 분기점까지 (X, Y) 중, 어떤 성분이 달라졌는지를 확인하고 해당 좌표까지를 전부 이어줍니다.
같은 방법으로 분기점에서 다음 분기점까지 달라진 성분을 찾은 후, 계속 이어주면 됩니다.
회로의 위치에 따라서 들어가는 비용이 달라지기 때문에 MAP 배열에 이어지는 회로를 저장해줬습니다.


다익스트라는 간단하게 구현 가능합니다.
시작점에서 시작해 4방향으로 이동 가능 하니, 4방향으로 갈 수 있는 곳을 찾아 이동합니다.
이동할 떄, 다른 회로 위에 있는지의 여부에 따라서 드는 비용을 다르게 계산해주면 됩니다.


마지막으로는 시작점과 방향이 달라지는 분기점, 끝점을 출력하는 것입니다.
먼저 이들을 찾으려면, 시작점부터 끝점까지 어느 좌표를 통해서 왔는지는 알아야합니다.
따라서, 다익스트라 탐색 중, 비용을 갱신하고 queue에 데이터를 넣을 때, 자신이 어느 좌표에서 왔는지를 저장해주면 됩니다.(부모를 저장해주면 됩니다.)

경로까지의 좌표들을 전부 구했다면, 이제 분기점을 찾아야합니다.
찾는 방법은 생각보다 간단한데, X좌표에서 다음 좌표인 Y까지 (X, Y) 중, 어떤 성분이 달라졌는지를 확인한 후, 달라진 성분을 바탕으로 계속 좌표를 이어나갑니다.
만약 이때, 성분이 달라지는 곳이 생긴다면 해당 정점이 분기점이 되는 것이기에 저장해주면 됩니다.

저장된 분기점 및 시작점과 끝점을 마지막에 출력해주면 됩니다.



자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <climits>
#define INF INT_MAX
#define F first
#define S second

using namespace std;

int N, M, K;
pair<int, int> st, fin;
int Map[51][51];
vector<pair<int, int>> circuit[8];
vector<pair<int, int>> way, ans;
int Distance[51][51];
pair<int, int> parent[51][51]; //방향, 좌표
int dx[4] = {1, -1, 0, 0}; // 하, 상, 우, 좌
int dy[4] = {0, 0, -1, 1};
priority_queue<pair<int, pair<int, int>>> q; // 비용, 좌표(X, Y)

void make_circuit(int st){
	for(int i = 0; i < circuit[st].size() - 1; i++){
		Map[circuit[st][i].F][circuit[st][i].S] = 1;
		if(circuit[st][i].F > circuit[st][i+1].F){ // 위로 올라가야할 때
			for(int j = circuit[st][i+1].F; j <= circuit[st][i].F; j++){
				Map[j][circuit[st][i].S] = 1;
			}
		}
		else if(circuit[st][i].F < circuit[st][i+1].F){ // 아래로 내려가야 할 떄
			for(int j = circuit[st][i].F; j <= circuit[st][i+1].F; j++){
				Map[j][circuit[st][i].S] = 1;
			}
		}
		else if(circuit[st][i].S > circuit[st][i+1].S){ // 왼쪽으로 가야할 때
			for(int j = circuit[st][i+1].S; j <= circuit[st][i].S; j++){
				Map[circuit[st][i].F][j] = 1;
			}
		}
		else if(circuit[st][i].S < circuit[st][i+1].S){ // 오른쪽으로 가야할 때
			for(int j = circuit[st][i].S; j <= circuit[st][i+1].S; j++){
				Map[circuit[st][i].F][j] = 1;
			}
		}
	}
	Map[circuit[st][circuit[st].size()-1].F][circuit[st][circuit[st].size()-1].S] = 1;
}

void reset_distance(){
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			Distance[i][j] = INF;
		}
	}
}

void Dijstra(){
	if(Map[st.F][st.S] == 1) Distance[st.F][st.S] = K;
	else Distance[st.F][st.S] = 1;	
	parent[st.F][st.S] = st;
	q.push({-Distance[st.F][st.S], st});
	while(!q.empty()){
		int x = q.top().S.F;
		int y = q.top().S.S;
		int cost = -q.top().F;
		q.pop();
		if(Distance[x][y] < cost) continue;
		for(int i = 0; i < 4; i++){
			int xx = x + dx[i];
			int yy = y + dy[i];
			if(xx >= 1 && xx <= N && yy >= 1 && yy <= N){
				if(Map[xx][yy] == 1){ //	회로 위에 있는 경우
					int n_cost = cost + K;
					if(Distance[xx][yy] > n_cost){
						parent[xx][yy] = {x, y}; // 현재 위치의 부모를 찾는다.
						Distance[xx][yy] = n_cost;
						q.push({-Distance[xx][yy], {xx, yy}});
					}
				}
				else{ // 회로 위에 없는 경우
					int n_cost = cost + 1;
					if(Distance[xx][yy] > n_cost){
						parent[xx][yy] = {x, y}; // 현재 위치의 부모를 찾는다.
						Distance[xx][yy] = n_cost;
						q.push({-Distance[xx][yy], {xx, yy}});
					}
				}
			}
		}
	}
}

void solve(){
	for(int i = 1; i <= M; i++){
		make_circuit(i);
	}
	reset_distance();
	Dijstra();
	////////////////////////////////////////////////// 지금까지 온 경로를 찾는다.
	pair<int, int> x = fin;
	while(1){
		if(x.F == st.F && x.S == st.S) break;
		way.push_back(x);
		x = parent[x.F][x.S];
	}
	way.push_back(st);
	////////////////////////////////////////////////// 경로를 바탕으로 꺾인 위치를 찾는다.
	ans.push_back(fin);
	int add_x = way[1].F - way[0].F, add_y = way[1].S - way[0].S; // 더해지는 값을 찾는다.
	for(int i = 1; i < way.size() - 1; i++){
		if(way[i].F + add_x != way[i+1].F || way[i].S + add_y != way[i+1].S){ // 더해지는 값이 다르다면 다른 방향으로 간 것이 된다.
			add_x = way[i + 1].F - way[i].F;
			add_y = way[i + 1].S - way[i].S;
			ans.push_back(way[i]);
		}
	}
	ans.push_back(st);
	//////////////////////////////////////////////////
	cout << Distance[fin.F][fin.S] << "\n";
	cout << ans.size() << " ";
	for(int i = ans.size()-1; i >= 0; i--){
		cout << ans[i].F << " " << ans[i].S << " ";
	}
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	cin >> st.F >> st.S >> fin.F >> fin.S;
	cin >> K;
	cin >> M;
	for(int i = 1; i <= M; i++){
		int t;
		cin >> t;
		for(int j = 1; j <= t; j++){
			int x, y;
			cin >> x >> y;
			circuit[i].push_back({x, y});
		}
	}
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.