BOJ 1348(주차장)풀이

solved.ac 티어 : 플래티넘 2

www.acmicpc.net/problem/1348

1348번: 주차장

 

bfs를 사용해서 각 자동차(C)마다 모든 주차구역(P)과의 거리를 저장해주고 이분 탐색하면서 이분 매칭으로 나올 수 있는 최솟값을 찾아주면 된다.

이분 탐색은 mid가 있을 때 각 자동차마다 주차구역을 가는 거리가 mid이하인 값들만 가지고 이분 매칭을 해주면 된다.

이때 이분매칭 했을 때의 값이 자동차 개수와 동일하다면 mid와 저장되어있는 최솟값을 비교하여 더 작을 경우 갱신해주면 된다.

(차의 개수가 0이거나 차의개수가 주차구역의 개수보다 많을경우만 따로 처리해주면 된다.)

 

import sys
from collections import deque
sys.setrecursionlimit(10**9)
def dfs(x,q,tt):
    for i in range(len(l[x])):
        y=l[x][i]
        if tt[y]:continue
        tt[y]=True
        if q[y]==-1 or dfs(q[y],q,tt):
            q[y]=x
            return True
    return False
def bfs(x):
    ch=[[-1 for i in range(b)]for g in range(a)]
    ch[car[x][0]][car[x][1]]=0
    q=deque([[car[x][0],car[x][1],0]])
    while q!=deque([]):
        y=q[0]
        for g in range(4):
            nx=y[1]+dx[g]
            ny=y[0]+dy[g]
            if nx<0 or nx>=b or ny<0 or ny>=a:
                continue
            if t[ny][nx]=="X":continue
            if ch[ny][nx]!=-1:continue
            ch[ny][nx]=y[2]+1
            q.append([ny,nx,y[2]+1])
        q.popleft()
    for i in range(pl):
        ck[x].append(ch[park[i][0]][park[i][1]])
def inp(x):
    l=[[] for i in range(cl+1)]
    for i in range(cl):
        for g in range(len(ck[i])):
            if ck[i][g]!=-1 and ck[i][g]<=x:
                l[i+1].append(g+1)
    return l
def pr(l,q,tt):
    q=[-1]*10001
    tt=[0]*10001
    cnt=0
    for i in range(cl):
        tt=[0]*10001
        if dfs(i+1,q,tt):
            cnt+=1
    #print("#",cnt)
    if cnt==cl:
        return 1
    return 0
q=[-1]*10001
tt=[0]*10001
a,b=map(int,input().split())
t=[list(input()) for i in range(a)]
car=[]
park=[]
dy=[-1,0,1,0]
dx=[0,1,0,-1]
ck=[[] for i in range(10001)]
for i in range(a):
    for g in range(b):
        if t[i][g]=="C":car.append([i,g])
        if t[i][g]=="P":park.append([i,g])
cl=len(car)
pl=len(park)
if cl==0:print(0);sys.exit()
if cl>pl:print(-1);sys.exit()
for i in range(cl):
    bfs(i)
left=0
right=3000
val=-1
while right-left>=0:
    m=(left+right)//2
    l=inp(m)
    if pr(l,q,tt):
        if val==-1:val=m
        else:val=min(val,m)
        right=m-1
    else:
        left=m+1
print(val)