BOJ 2570(비숍 2)풀이

solved.ac 티어 : 플래 2

www.acmicpc.net/problem/2570

2570번: 비숍2

이문제는 joseph0528.tistory.com/30

BOJ 9525(룩 배치하기)풀이

이 문제랑 별 차이가 없다. 다른 점은 룩 문제는 가로, 세로이지만 비숍 문제는 대각선이라는 거밖에 없다. 비숍 문제도 왼쪽 아래 대각선이랑 오른쪽 아래 대각선을 구해주면 끝이다.

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())
b=int(input())
r=[[0 for i in range(a)]for g in range(a)]
M=[[0 for i in range(101)]for g in range(101)]
l=[[] for i in range(5001)]
for i in range(b):
    c,d=map(int,input().split())
    r[c-1][d-1]=1
nx=[]
ny=[]
xcnt=0
ycnt=0
x=0
def A(y,x):
    global nx,xcnt
    p=[-1,0,0,0]
    while y<=a-1 and x<=a-1:
        if r[y][x]==1:
            if p[0]!=-1:nx.append(p)
            p=[-1,0,0,0]
        else:
            if p[0]==-1:xcnt+=1;p[0]=y;p[1]=x
            l[xcnt].append(M[y][x])
            p[2]=y;p[3]=x
        x+=1
        y+=1
    if p[0]!=-1:nx.append(p)
def B(y,x):
    global ny,ycnt
    p=[-1,0,0,0]
    while y>=0 and x<=a-1:
        if r[y][x]==1:
            if p[0]!=-1:ny.append(p)
            p=[-1,0,0,0]
        else:
            if p[0]==-1:ycnt+=1;p[0]=y;p[1]=x
            M[y][x]=ycnt
            p[2]=y;p[3]=x
        y-=1
        x+=1
    if p[0]!=-1:ny.append(p)
for i in range(a):y=i;x=0;B(y,x)
for i in range(1,a):y=a-1;x=i;B(y,x)
for i in range(a):y=a-i-1;x=0;A(y,x)
for i in range(1,a):y=0;x=i;A(y,x)
#print(nx)
#print(ny)
maxr=max(ycnt,xcnt)
#for i in range(a):
#    for g in range(a):
#        print(M[i][g],end=" ")
#    print()
#print()
#print(l)

q=[0]*(maxr+1)
t=[0]*(maxr+1)
cnt=0
for i in range(maxr):
    t=[0]*(maxr+1)
    if dfs(i+1):
        cnt+=1
print(cnt)