[BOJ/Platinum 2] 백준 1348 주차장(C++)

문제 링크

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

 

문제

세준 주차장은 R×C크기의 직사각형 모양이다. 세준 주차장에는 N개의 차와, M개의 주차 구역이 있다. 그리고, 모든 차는 주차 구역에 주차하려고 한다. 교통 제한 때문에, 차는 주차장의 경계와 평행하게만 움직일 수 있고, 모든 차는 1초에 한 칸씩 움직일 수 있다.

보통 모든 차는 현재 위치에서 가장 가까운 위치에 있는 주차 구역에 주차를 하려고 한다. 하지만, 다음과 같이 생긴 주차장이라면 현재 위치에서 가장 가까운 위치에 주차하는 것이 비효율적이다.

.C.....P.X...
XX.......X..P
XX.....C.....

 

‘C’는 차이고, 'P‘는 주차 구역, 'X'는 벽이고, '.'은 빈 공간이다.

만약 아래에 있는 차가 현재 위치에서 가장 가까운 곳에 주차를 한다면, 왼쪽 위에 있는 차는 가장 오른쪽에 있는 주차 구역에 주차를 해야 할 것이다. 이렇게 되면, 그 차가 주차하기 까지 14라는 시간이 걸린다. 하지만, 만약 아래에 있는 차가 오른 쪽에 있는 주차 구역에 주차를 하게 된다면, 두 차가 주차하기 까지 6이라는 시간이 걸린다.

현재 주차장의 모양과, 차의 위치, 주차 구역의 위치가 주어졌을 때, 모든 차가 주차하는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오. 차는 매우 작기 때문에, 한 칸에 여러 대의 차가 동시에 들어갈 수 있다. 차는 빈 공간과, 주차 구역만 통과할 수 있지만, 벽은 통과할 수 없다.

만약 모든 차가 주차하는 것이 불가능하다면, -1을 출력한다.

 

입력

첫째 줄에 주차장의 세로 크기 R과 가로 크기 C가 주어진다. R과 C의 크기는 50보다 작거나 같다. 둘째 줄부터 R개의 줄에는 주차장의 정보가 주어진다. 주차장의 정보는 문제에서 설명한 문자로 이루어져 있다. 차의 개수와, 주차 구역의 개수는 모두 0보다 크거나 같고 100을 넘지 않는다.

 

출력

첫째 줄에 모든 차가 주차하는데 걸리는 시간의 최솟값을 출력한다. 차가 없는 경우는 0을 출력한다.

 

예제 입력 1

3 7
C.....P
C.....P
C.....P

예제 출력 1

6

예제 입력 2

4 8
C.X.....
..X..X..
..X..X..
.....X.P

예제 출력 2

16

예제 입력 3

6 11
XXXXXXXXXXX
X......XPPX
XC...P.XPPX
X......X..X
X....C....X
XXXXXXXXXXX

예제 출력 3

5

예제 입력 4

5 3
.C.
...
C.C
X.X
PPP

예제 출력 4

4

예제 입력 5

3 5
CCCCC
.....
PXPXP

예제 출력 5

-1

예제 입력 6

3 5
..X..
C.X.P
..X..

예제 출력 6

-1

 

알고리즘 분류

• 그래프 탐색
• 이분 탐색
• 이분 매칭

 

풀이

차 한 대당 주차 구역 하나에 주차해야 하고, 모든 차가 주차 구역에 주차를 해야 하므로 이분 매칭을 이용한다.

먼저, 모든 차를 큐에 push하고, 모든 주차 구역에 도달할 수 있는 최소의 시간을 BFS를 이용하여 구한다.

모든 차가 각각의 주차 구역까지 도달하는 최소의 시간을 기록해야 한다.

그리고, 도출될 수 있는 모든 이동 시간들을 하나의 배열로 관리한다. 이 배열을 정렬하고 중복을 제거한 후, Left를 0, Right를 이동 시간의 최댓값 + 1로 정하고 이동 시간에 대한 이분 탐색을 수행한다.

Mid는 (Left + Right) / 2이며, 이 Mid의 시간 내에 모든 차가 주차 구역에 주차할 수 있는지를 이분 매칭을 통해 확인한다.

이분 매칭을 할 때, 어떤 차가 어떤 주차 구역까지 Mid의 시간 내에 도달할 수 없다면 해당 차와 주차 구역을 매칭시켜서는 안 된다.

매칭된 차와 주차 구역 쌍이 차의 대수만큼 나오도록 주차할 수 있다면 Right를 Mid로 초기화시키고 이분 탐색을 다시 수행한다. 그럴 수 없다면 Mid 이하의 이동 시간을 탐색하는 것은 의미가 없으므로 Left를 Mid + 1로 초기화시키고 이분 탐색을 다시 수행한다.

Left가 Right를 넘어서게 되면 이분 탐색을 종료하며, 마지막에 결정된 Right 값이 우리가 구하는, 모든 차가 주차하는 데 걸리는 최소의 시간이 된다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 51
#define INF 1e9
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int R, C;
int MAP[MAX][MAX];
vector<pair<int, int> > Cars, Parkings;
int ParkingNum[MAX][MAX];
int Visited[MAX][MAX][MAX * 2];
int Time[MAX * 2][MAX * 2];
int MoveY[4] = { -1,0,1,0 };
int MoveX[4] = { 0,-1,0,1 };
int CMatch[MAX * 2], PMatch[MAX * 2];
bool PVisited[MAX * 2];
vector<int> Times;
int Answer = INF;

void init() {
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			for (int k = 0; k < (MAX * 2); k++) {
				Visited[i][j][k] = INF;
			}
		}
	}
	for (int i = 0; i < (MAX * 2); i++) {
		for (int j = 0; j < (MAX * 2); j++) {
			Time[i][j] = INF;
		}
	}
}

void init2() {
	for (int i = 0; i < (MAX * 2); i++) {
		CMatch[i] = -1;
		PMatch[i] = -1;
	}
}

void init3() {
	for (int i = 0; i < (MAX * 2); i++) {
		PVisited[i] = false;
	}
}

void input() {
    cin >> R >> C;
    for (int i = 0; i < R; i++) {
        string S;
		cin >> S;
		for (int j = 0; j < C; j++) {
			char Now = S[j];
			if (Now == 'C') {
				Cars.push_back(make_pair(i, j));
			}
			else if (Now == 'P') {
				MAP[i][j] = 1;
				ParkingNum[i][j] = (int)Parkings.size();
				Parkings.push_back(make_pair(i, j));
			}
			else if (Now == 'X') {
				MAP[i][j] = -1;
			}
		}
    }
}

void bfs() {
	queue<pair<pair<int, int>, pair<int, int> > > Q;
	for (int i = 0; i < (int)Cars.size(); i++) {
		Q.push(make_pair(Cars[i], make_pair(i, 0)));
		Visited[Cars[i].first][Cars[i].second][i] = true;
	}

	while (!Q.empty()) {
		int NowY = Q.front().first.first;
		int NowX = Q.front().first.second;
		int NowC = Q.front().second.first;
		int NowT = Q.front().second.second;
		Q.pop();

		if (MAP[NowY][NowX] == 1) {
			Time[NowC][ParkingNum[NowY][NowX]] = min(Time[NowC][ParkingNum[NowY][NowX]], NowT);
		}

		for (int i = 0; i < 4; i++) {
			int NextY = NowY + MoveY[i];
			int NextX = NowX + MoveX[i];
			if ((NextY < 0) || (NextY >= R) || (NextX < 0) || (NextX >= C)) continue;
			if (MAP[NextY][NextX] == -1) continue;
			if (Visited[NextY][NextX][NowC] > NowT + 1) {
				Q.push(make_pair(make_pair(NextY, NextX), make_pair(NowC, NowT + 1)));
				Visited[NextY][NextX][NowC] = NowT + 1;
			}
		}
	};
}

bool dfs(int MidTime, int Car) {
	for (int i = 0; i < (int)Parkings.size(); i++) {
		int ParkingTime = Time[Car][i];
		if (ParkingTime > MidTime) continue;
		if (!PVisited[i]) {
			PVisited[i] = true;
			if ((PMatch[i] == -1) || dfs(MidTime, PMatch[i])) {
				CMatch[Car] = i;
				PMatch[i] = Car;
				return true;
			}
		}
	}

	return false;
}

void bipartiteMatching() {
	int Left = 0;
	int Right = (int)Times.back() + 1;

	while (Left < Right) {
		init2();
		int Mid = (Left + Right) / 2;
		int Matched = 0;
		for (int i = 0; i < (int)Cars.size(); i++) {
			init3();
			if (dfs(Mid, i)) {
				Matched++;
			}
		}

		if (Matched == (int)Cars.size()) {
			Right = Mid;
			Answer = min(Answer, Right);
		}
		else {
			Left = Mid + 1;
		}
	};
}

void settings() {
	bfs();
	if (Cars.empty()) {
		Answer = 0;
		return;
	}
	for (int i = 0; i < (int)Cars.size(); i++) {
		for (int j = 0; j < (int)Parkings.size(); j++) {
			if (Time[i][j] < INF) {
				Times.push_back(Time[i][j]);
			}
		}
	}
	sort(Times.begin(), Times.end());
	Times.erase(unique(Times.begin(), Times.end()), Times.end());
	if (!Times.empty()) {
		bipartiteMatching();
	}
}

void printAnswer() {
	if (Answer == INF) {
		cout << "-1\n";
	}
	else {
    	cout << Answer << "\n";
	}
}

int main() {
    FASTIO

    init();
    input();
    settings();
    printAnswer();

    return 0;
}