BOJ 1574(룩 어택)풀이

solved.ac 티어 : 플래티넘 4

www.acmicpc.net/problem/1574

1574번: 룩 어택

 

이문제는 한 행 과열에 단 한 개의 룩을 놔서 최대한 많이 놓은 개수를 출력하는 문제이다. 정말 간단한 이분 매칭 문제다.

행과 열에 한 개만 놓을 수 있다는 것은 행 또는 열을 잡고 자신이 놓을 수 있는 곳에 이분 매칭을 해주면 된다. 하지만 여기서 빈칸이 생기는데 그래도 공격이 막히지는 않으니 입력 위치가 아니면서 놓을 수 있는 곳들을 이분 매칭 해주면 된다.

예시 입력을 예를 들겠다.

왼쪽은 열, 오른쪽은 행이다.

평범한 룩 문제였으면 이분매칭이 이렇게 됐겠지만

이건 놓을 수 없는 곳이 있기때문에 놓을수 없는곳들을 빼주면

이렇게 되면서 놓을수 있는 최대 개수는 2개가 된다.

이 코드를 짜서 제출하면 정답이다.

def dfs(x):
    for i in range(1,b+1):
        if l[x][i]==1:continue
        y=i
        if t[y]:continue
        t[y]=True
        if q[y]==0 or dfs(q[y]):
            q[y]=x
            return True
    return False
a,b,c=map(int,input().split())
l=[[0 for g in range(301)] for i in range(301)]
for g in range(c):
    d,e=map(int,input().split())
    l[d][e]=1
q=[0]*301
t=[0]*301
cnt=0
for i in range(a):
    t=[0]*301
    if dfs(i+1):
        cnt+=1
print(cnt)