BOJ 9525(룩 배치하기)풀이

solved.ac 티어 : 플래 3

www.acmicpc.net/problem/9525

9525번: 룩 배치하기

이 그림은 노란색 행을 선택했을 때 선택될 수 있는 초록색 열이다.

 

이 그림은 파란색 행을 선택했을때 선택될수 있는 보라색 열이다.

이거처럼 행을 기준으로 나올 수 있는 열에 번호를 매겨서 이분 매칭을 해주면 된다.

위 그림을 번호를 매겨 줬을 때

 

(열)

빨간색은 1, 주황색은 2, 노란색은 3, 초록색은 4, 하늘색은 5, 보라색은 6, 핑크색은 7로 잡아주고(번호는 딱히 순서대로가 아니여도 된다.)

 

행

빨강색은 1,주황색은 2, 노랑색은 3,초록색은 4, 하늘색은 5, 보라색은 6으로 잡아주고 이분 매칭을 해주면(행이나 열이나 방법은 같다)

복잡하게 생겼지만 이렇게 된다.

 

import sys
sys.setrecursionlimit(10**9)
input=sys.stdin.readline
def dfs(x):
    for i in range(len(l[x])):
        y=l[x][i]
        if t[y]:continue
        t[y]=True
        if q[y]==0 or dfs(q[y]):
            q[y]=x
            return True
    return False
a=int(input())
n=[list(input()) for i in range(a)]
y1=[]
x1=[]
ycnt=0
xcnt=0
p=[-1,-1,-1,-1]
for i in range(a):
    p=[-1,-1,-1,-1]
    for g in range(a):
        if n[g][i]=="X":
            if p[0]!=-1:y1.append(p)
            p=[-1,-1,-1,-1]
        else:
            if p[0]==-1:ycnt+=1;p[0]=g;p[1]=i
            p[2]=g;p[3]=i
    if p[0]!=-1:y1.append(p)
for i in range(a):
    p=[-1,-1,-1,-1]
    for g in range(a):
        if n[i][g]=="X":
            if p[0]!=-1:x1.append(p)
            p=[-1,-1,-1,-1]
        else:
            if p[0]==-1:xcnt+=1;p[0]=i;p[1]=g
            p[2]=i;p[3]=g
    if p[0]!=-1:x1.append(p)
#print(y1)
#print(x1)
maxr=max(ycnt,xcnt)
l=[[] for i in range(maxr+1)]
q=[0]*(maxr+1)
t=[0]*(maxr+1)
for i in range(ycnt):
    for g in range(xcnt):
        if(y1[i][0]<=x1[g][0]<=y1[i][2])and(x1[g][1]<=y1[i][1]<=x1[g][3]):
            l[i+1].append(g+1)
#print(l)
cnt=0
for i in range(maxr):
    t=[0]*(maxr+1)
    if dfs(i+1):
        cnt+=1
print(cnt)