[백준]1348 주차장

문제소개

---

1348주차장은 이분매칭 + 이분탐색 문제입니다. 차 한대씩 주차 공간 1곳에 주차하는 것이기 때문에 직관적으로 이분매칭을 생각할 수 있습니다. 저는 이 문제를 MCMF 그러니깐 SPFA로 해결하려고 시도했다가 "아 그러면 안되는 구나"를 깨달았고 SPFA와 이분매칭을 조금더 생각할 수 있었습니다. 

 

 

문제풀이

---

3 13
.C.....P.X... XX.......X..P XX.....C.....

문제는 다음과 같은 입력값을 받습니다. 그러므로 각각의 차들에서 각각의 주차공간까지 최단거리를 계산해야 합니다. 이때 계산은 BFS로 진행합니다. 그리고 계산한 최단경로 값을 노드와 엣지로 정리합니다.

왼쪽이 차량이며 오른쪽이 주차공간입니다. 

다음 그래프에서는 2가지 경우의 이분매칭을 만들 수 있습니다. 

 

1 ⇒ 2 : 14, 2 ⇒ 1 : 2  

주차하는데 걸리는 시간은 총 : 14

 

1 ⇒ 1 : 6, 2 ⇒ 2 : 6  

주차하는데 걸리는 시간은 총 : 6

 

MCMF는 간선의 비용의 최소합을 구하는 것지만 1348 주차장 문제는 이분 매칭되는 경우에서 최대 비용 간선을 찾는 문제입니다.

 

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

예를들어 다음과 같은 입력일 때 다음과 같은 그래프를 만들 수 있습니다.

 

위 그래프에서 만들 수 있는 모든 경우의 최소합이 24라는 것을 알 수 있습니다. 그러므로 Augment Path로 MCMF를 찾는 SPFA 알고리즘은 10-8-6(24)의 경우만 찾을 것으로 저는 판단했습니다. 위 예시의 답은 8입니다. 혹시 방법이 있으시면 조언을 부탁드립니다. 

 

그래서 다시 이분매칭으로 문제를 접근했습니다. 

먼저 해당 그래프에서 모든 차들을 주차할 수 있는지를 확인 합니다. 

만약 주차가 가능하다면 주차 시간이 최소가 되는 매칭을 찾아야합니다.

이때 이분 탐색을 통해 최소 주차 시간을 찾습니다. (DFS를 최소화하기 위해서)

 

---

소스보기