한 달 전에 이분 매칭을 한창 공부할 때, 시도해서 틀렸다가 나중에 풀어야지 하고 잠깐 다른 공부하러 갔던 한 문제가 있었는데
문제 자체가 꽤 재밌어서 그런지 잊지 않고 있다가 오늘 풀어냈다.
그 문제가 바로 이 문제..!

BOJ 1348 - 주차장 링크
(2022.09.06 기준 P2)
(치팅하면 평생 가는 주차장마다 자리 없음 ㅎ)

문제

R×C크기의 주차장에 N개의 차와 M개의 주차 구역이 있다면
모든 차가 주차하는데 걸리는 시간의 최솟값

알고리즘

한 주차장엔 한 자동차만 주차할 수 있다. 전형적인 이분 매칭.
근데 자동차와 주차장 간 거리가 주어져 있지 않다. 그래서 BFS로 직접 거리를 구해줘야 한다.
그리고 이분 탐색. 이는 풀이에서 후술.

풀이

R, C, 주차장 상태가 입력으로 주어진다.
먼저, 주차장 상태를 받은 행렬에서 주차장와 자동차의 수와 위치를 저장하자.

이 때, 위치를 저장하는 방법은 각자 알아서 하면 되지만 나는 다음과 같아 했다.

cars = parkings = 0 # 자동차 수, 주차장 수
carR = []; carC = [] # 자동차 행과 열 위치
for r in range(R):
	for c in range(C):
    	if matrix[r][c] == 'C': # 자동차면
        	cars += 1 # 자동차 수 증가
            carR.append(r) # 자동차 행 저장
            carC.append(c) # 자동차 열 저장
        elif matrix[r][c] == 'P': # 주차장이면
        	matrix[r][c] = parkings # 행열에 주차장 번호 저장
            parkings += 1 # 주차장 수 증가

이렇게 하면 나중에 자동차와 주차장 간 거리를 구할 때 편해진다.

그리고 자동차가 없다면 0을 출력, 자동차가 주차장보다 많으면 전부 주차가 불가능하므로 -1을 출력하자.


위 두 경우에 해당하지 않으면 이제 자동차와 주차장 간 거리를 구해줘야 한다.
아까 구했던 위치를 이용해 모든 자동차와 주차장 간 거리를 구해주자.
BFS를 이용하여 구하면 되는데 방법은 생략하겠다. (모르겠으면 이 문제 풀고 있을 실력이 아직 아닌거임..)

이 후, 이분 매칭을 하여 답을 구하는 것을 누구나 생각할 수 있는 과정.
여기부터 중요하다.

나는 처음에 자동차 하나하나 이분 매칭을 시도할 때 주차장과의 거리를 오름차순으로 정렬하여 매칭했는데 실패.
후에 매칭되는 주차장이 제일 짧은 거리인 주차장과의 매칭을 밀어냈다.

그러면 밀어내니깐 아예 처음부터 거리를 내림차순으로 정렬하여 매칭해볼까? 했지만 실패.
이것도 서로 매칭을 밀어내니 답이 없었다.

사실 이 방법들은 전부 틀렸다.
이 문제는 주차하는데 걸리는 시간의 최솟값. 하나가 짧거나 길면 다른 하나는 길어지거나 짧아진다. 그래서 최솟값을 구하려면 모든 주차 시간이 최대한 비슷하게 어우려지면서 작아져야 하니, 그리디하게 풀리지 않는 문제이다.

설명을 제대로 못했지만 대충 쉽게 이해했을 것이다.
그럼 어떻게 해야 하냐..
바로 매칭 가능한 거리를 임의로 줄이거나 늘리면서 답을 찾아가는 것이다.
여기서 쓰이는 것이 이분 탐색.

시작과 끝을 잡고 그 중간 거리로 하여금 매칭을 시도한다.
모든 자동차이 주차장과 매칭이 됐으면, 욕심을 부려 거리를 줄여봐서 다시 시도.
만약 모든 자동차가 매칭이 불가능했으면, 너무 욕심을 부린 것이기 때문에 거리를 늘려줘야 한다.
이를 이분으로 범위를 좁혀 나가면서 주차 시간의 최솟값을 구해나가면 된다.

코드

import sys; input = sys.stdin.readline
from math import inf
from collections import deque

# 이분 매칭
def match(p):
    for q, d in enumerate(distance[p]):
        if not visited[q] and d < mid: # 거리가 이분 탐색의 mid 보다 적어야 한다.
            visited[q] = True
            if connect[q] == -1 or match(connect[q]):
                connect[q] = p
                return True
    return False

R, C = map(int, input().split())
matrix = [list(input().strip()) for _ in range(R)]
cars = parkings = 0 # 자동차 수, 주차장 수
carR = []; carC = [] # 자동차 행, 자동차 열
for r in range(R):
    for c in range(C):
        if matrix[r][c] == 'C': # 자동차면 자동차 수 증가 및 위치 저장
            cars += 1
            carR.append(r)
            carC.append(c)
        elif matrix[r][c] == 'P': # 주차장이면 주차장 번호를 넣어주고 주차장 수 증가
            matrix[r][c] = parkings # 이렇게 하면 주차장 번호는 0부터 차례대로 들어간다.
            parkings += 1

# 자동차가 없으면 0 출력
if not cars:
    print(0)
    exit()
# 자동차가 주차장보다 많으면 전부 주차가 불가능하므로 -1 출력
if cars > parkings:
    print(-1)
    exit()

# 자동차와 주차장 간 거리를 구하자.
distance = [[inf] * parkings for _ in range(cars)]
for i in range(cars): # 자동차 차례대로
    visited = [[False] * C for _ in range(R)]
    queue = deque([(carR[i], carC[i], 0)]) # 아까 구했던 위치로 하여금 덱을 생성
    visited[carR[i]][carC[i]] = True
    rest = parkings # 남은 주차장
    while queue: # BFS 시작
        r, c, t = queue.popleft() # 행, 열, 시간(거리)
        if isinstance(matrix[r][c], int): # 현재 위치가 정수이면 주차장이다.
            distance[i][matrix[r][c]] = t # 자동차와 주차장 간 거리 저장
            rest -= 1 # 남은 주차장은 줄어든다. 남은 주차장이 없다면 탐색 중지
            if not rest:
                break
        for rr, cc in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]: # 상하좌우
            if 0 <= rr < R and 0 <= cc < C and matrix[rr][cc] != 'X' and not visited[rr][cc]:
                visited[rr][cc] = True
                queue.append((rr, cc, t + 1))

# 거리를 구하면 이분 탐색으로 하여금 이분 매칭 시작
# mid보다 작은 거리로만 이분 매칭하면서 답을 구해나감
start = 0; end = 2500 # 가로 세로 크기가 최대 50이므로 end를 넉넉하게 2500으로 잡자.
answer = inf
while True:
    mid = (start + end) // 2
    connect = [-1] * parkings
    for i in range(cars): # 이분 매칭
        visited = [False] * parkings
        if not match(i):
            break # 만약 자동차 하나라도 주차가 불가능하면 중지
    else: # 자동차 전부가 주차되었다면
        result = 0
        for p, c in enumerate(connect):
            if c > -1:
                result = max(result, distance[c][p]) # 매칭된 자동차와 주차장 간의 거리들의 최댓값을 구하고
        answer = min(answer, result) # 출력값보다 작으면 출력값으로 저장
        end = mid # 주차가 되었으니 거리를 줄여봐야 한다.
        if start == end: # 시작과 끝이 같으면 중지
            break
        continue
    # 만약 주차가 불가능했다면
    start = mid + 1 # 거리를 늘려야 한다.
    if start == end: # 시작과 끝이 같으면 중지
        break

# 출력값이 갱신되었다면 그대로 출력. 아니면 모든 거리가 불가능했다는 것이므로 -1 출력
print(answer) if answer < inf else print(-1)

여담

이분 탐색을 자주 쓰지 않지만, 쓸 때마다 느끼는 것이 있는데
이분 탐색은 정말 간단하고 강력한 해결 방법인 것 같다.