[백준 1348번] 파이썬 - 주차장

백준 1348 - 주차장

시간 제한 1초, 메모리 제한 256MB

# 조건

• 세준 주차장은 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을 출력한다.

# 접근 방법

• 입력받은 주차장의 정보에서 자동차와 주차 구역의 위치를 기록해준다.
  • 우선, 차가 없다면 0을 출력, 주차 구역의 수가 자동차의 수보다 적다면 -1을 출력해준다.
• 이후 BFS를 활용하여 각 차에서 모든 주차 구역까지의 거리를 구해주면 된다.
• 또한, 구해진 모든 자동차를 주차 구역에 매칭해주기 위해서는 이분 매칭을 이용하여 풀어주면 되는데 이 부분이 어려웠다.
• 아이디어를 생각하다가 이분 탐색을 이용하여 임의의 거리를 정해준 후 매칭을 시도해주었다.
  • 모든 자동차가 매칭이 완료되었다면 거리를 줄여가며 매칭을하고
  • 자동차가 매칭이 불가능 했다면 거리를 늘려가며 매칭해주면 된다.
• 이분 매칭의 경우
• 현재 구역에 방문하지 않았고, MID 보다 거리가 짧다면
  • 현재 구역에 주차할 수 있거나, 현재 구역에 주차되어있는 차를 옮길 수 있는지 체크해주면서 모든 차를 체크해주면 된다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  

def bfs(x, y, num):  
    q = deque()  
    q.append((x, y))  
    visited = [[-1] * C for _ in range(R)]  
    visited[x][y] = 0  
    while q:  
        si, sj = q.popleft()  
        # 현재가 주차구역이면 표시된 주차 구역까지의 거리 기록해주기  
        if isinstance(parking_lot[si][sj], int):  
            dist[num][parking_lot[si][sj]] = visited[si][sj]  
        for d in range(4):  
            ni, nj = si+di[d], sj+dj[d]  
            if 0<=ni<R and 0<=nj<C and visited[ni][nj] == -1 and parking_lot[ni][nj] != 'X':  
                q.append((ni, nj))  
                visited[ni][nj] = visited[si][sj] + 1  

def matching(num):  
    for idx, d in enumerate(dist[num]):  
        # 주차 자리를 방문하지 않았고 mid의 거리보다 짧다면  
        if not visited[idx] and d < mid:  
            visited[idx] = True  
            # 현재 주차하려는 곳이 비어있거나 다른 차가 있다면  
            # 다른 차를 옮겨 주기            # 옮겼다면 return 1, 옮기지 못했다면 return 0            
            if now[idx] == -1 or matching(now[idx]):  
                now[idx] = num  
                return 1  

    return 0  


R, C = map(int, input().split())  
parking_lot = [list(input().rstrip()) for _ in range(R)]  

cars, parking = [], []  
cnt = 0  
for i in range(R):  
    for j in range(C):  
        if parking_lot[i][j] == 'C':  
            cars.append([i, j])  
        elif parking_lot[i][j] == 'P':  
            # 주차 구역을 번호로 변경해주기  
            parking.append([i, j])  
            parking_lot[i][j] = cnt  
            cnt += 1  

if not cars:  
    print(0)  
    exit()  

if len(cars) > len(parking):  
    print(-1)  
    exit()  

# 자동차와 모든 주차구역까지의 거리 구하기  
dist = [[float('inf')] * len(parking) for _ in range(len(cars))]  
di, dj = [1, -1, 0 , 0], [0, 0, -1, 1]  
for idx, val in enumerate(cars):  
    bfs(val[0], val[1], idx)  

# 이분 탐색으로 이분 매칭 시작해주기  
start, end = 0, R*C+1  
answer = float('inf')  
while  True:  
    mid = (start + end) // 2  
    # 현재 주차 구역에 차가 있는지 표시  
    now = [-1] * len(parking)  
    # 이분 매칭 시작  
    for i in range(len(cars)):  
        visited = [False] * len(parking)  
        val = matching(i)  
        if not val:  
            break  

    # 모든 차를 주차할 수 있다면  
    else:  
        temp = 0  
        for idx, d in enumerate(now):  
            # 매칭된 자동차와 주차 구역 간의 최대 거리 구해주고  
            # 최솟값으로 갱신            
            if d > -1:  
                temp = max(temp, dist[d][idx])  

        answer = min(answer, temp)  
        # 모든 차를 주차할 수 있다면 거리 줄여보기  
        end = mid  
        if start == end:  
            break  
        continue  
    # 주차 불가능하면 거리 늘려주기  
    start = mid + 1  
    if start == end:  
        break  
print(answer if answer < float('inf') else -1)