[백준/BOJ] 백준 2645번 : 회로배치

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

2645번: 회로배치

 

이미 회로가 놓인 위치를 2차원 배열에 표시해 놓고, 다익스트라 알고리즘을 통해 시작 지점부터 도착 지점까지 도달하는데 최소비용을 계산했다.

이때 최소비용을 계산하면서, come_from[55][55] 에 해당 위치로 오기 전에 직전에 어떤 위치에 있었는지 저장해 놓고, 도착 지점까지 최소 비용 계산이 끝나면 come_from[55][55]을 이용해 도착지점부터 시작지점까지 거꾸로 확인하면서 이동 경로를 확인하는 방법으로 문제를 해결했다.

 

코드

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

int n;
pair<int, int> start;
pair<int, int> dest;
int k;
int input1, input2;
vector<vector<int>> board(55, vector<int>(55, 0));
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
pair<int, int> come_from[55][55]; //해당 위치로 오기 전에 어디를 지나 왔는지 저장
int result1;
vector<pair<int, int>> result2;

//목적지까지 최소 비용 구하기
void Solve1() {
	vector<vector<int>> s_dist(55, vector<int>(55, 987654321));
	priority_queue<pair<int, pair<int, int>>> pq; //(-cost,(위치))

	//시작 위치가 회로가 배치되지 않은 위치일때
	if (board[start.first][start.second] == 0) {
		s_dist[start.first][start.second] = 1;
	}

	//시작 위치가 회로가 배치된 위치일때
	else {
		s_dist[start.first][start.second] = k;
	}

	pq.push(make_pair(-s_dist[start.first][start.second], start));

	while (!pq.empty()) {
		int here_cost = -pq.top().first;
		pair<int, int> here = pq.top().second;
		pq.pop();

		if (s_dist[here.first][here.second] < here_cost) {
			continue;
		}

		//목적지에 도착했을때
		if (here == dest) {
			result1 = here_cost;
			return;
		}

		for (int dir = 0; dir < 4; dir++) {
			pair<int, int> there = make_pair(here.first + dxdy[dir][0], here.second + dxdy[dir][1]);
			int there_cost;

			if (there.first <= 0 || here.first > n || here.second <= 0 || here.second > n) {
				continue;
			}

			//회로가 배치된 위치일때
			if (board[there.first][there.second] == 1) {
				there_cost = here_cost + k;
			}

			//회로가 배치되지 않은 위치일때
			else {
				there_cost = here_cost + 1;
			}

			if (s_dist[there.first][there.second] > there_cost) {
				s_dist[there.first][there.second] = there_cost;
				pq.push(make_pair(-there_cost, there));

				//there 지점으로 오는데 어디를 거쳐서 왔는지 저장
				come_from[there.first][there.second] = here;
			}
		}
	}
}

//이동 경로 확인
void Solve2() {

	//도착지점부터 시작지점까지 거꾸로 가면서 이동 경로 확인
	pair<int, int> here = dest;
	result2.push_back(here);

	int dir = -1; //-1:초기값 1:수평이동, 2:수직이동
	while (1) {

		if (here == start) {
			result2.push_back(here);
			break;
		}

		pair<int, int> there = come_from[here.first][here.second];

		if (there.first == here.first) { //수평으로 움직이는 방향일때
			if (dir == -1) {
				dir = 1;
				here = there;
			}
			else if (dir == 1) {
				dir = 1;
				here = there;
			}
			else if (dir == 2) { //here이 방향이 꺾이는 지점일때
				result2.push_back(here);
				dir = 1;
				here = there;
			}
		}

		else { //수직으로 움직이는 방향일때
			if (dir == -1) {
				dir = 2;
				here = there;
			}

			else if (dir == 1) { //here이 방향이 꺾이는 지점일때
				result2.push_back(here);
				dir = 2;
				here = there;
			}

			else if (dir == 2) {
				dir = 2;
				here = there;
			}
		}
	}

	reverse(result2.begin(), result2.end());
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	cin >> input1 >> input2;
	start = make_pair(input1, input2);

	cin >> input1 >> input2;
	dest = make_pair(input1, input2);

	cin >> k;

	int b_num;
	cin >> b_num;

	for (int i = 0; i < b_num; i++) {
		int p_num;
		cin >> p_num;

		pair<int, int> before = make_pair(-1, -1);

		for (int j = 0; j < p_num; j++) {
			cin >> input1 >> input2;
			pair<int, int> here = make_pair(input1, input2);

			//처음 시작 점일때
			if (before.first == -1) {
				board[here.first][here.second] = 1;
				before = here;
				continue;
			}

			if (before.first == here.first) { //수평으로 움직이는 방향일때

				if (before.second < here.second) { //오른쪽으로 움직이는 방향일때

					for (int k = before.second; k <= here.second; k++) {
						board[here.first][k] = 1;
					}

				}

				else { //왼쪽으로 움직이는 방향일때

					for (int k = before.second; k >= here.second; k--) {
						board[here.first][k] = 1;
					}
				}

			}

			else if (before.second == here.second) { //수직으로 움직이는 방향일때

				if (before.first < here.first) { //위쪽으로 움직이는 방향일때

					for (int k = before.first; k <= here.first; k++) {
						board[k][here.second] = 1;
					}

				}

				else { //아래쪽으로 움직이는 방향일때

					for (int k = before.first; k >= here.first; k--) {
						board[k][here.second] = 1;
					}
				}
			}

			before = here;
		}
	}

	Solve1();
	Solve2();

	cout << result1 << "\n";
	cout << result2.size() << " ";
	for (int i = 0; i < result2.size(); i++) {
		cout << result2[i].first << " " << result2[i].second << " ";
	}

	return 0;
}