백준 1574 룩 어택

작성일 | In |

문제 링크

  • https://www.acmicpc.net/problem/1574

알고리즘

  • 이분 매칭

풀이

이 문제는 ‘열혈강호’나 ‘축사배정’과 같은 문제와 달리 이분 매칭에 필요한 정점들을 직접 만들어야 한다. 처음엔 정점을 어떻게 구현하는지 몰라서 여러 번의 실패를 겪어야만 했다.

https://www.crocus.co.kr/765

위의 블로그 글을 본 후에야 방법을 알게 되었는데, 사실 저 방법조차도 이해하는 데에 오랜 시간이 걸렸다. 열과 행 기준으로 그룹을 구성하고 숫자를 매기는 작업을 한 번씩 실시해야 한다. 무슨 말이냐면 특정 열 혹은 행에서 룩이 얼마나 놓일 수 있는지 계산하는 작업이다.

예를 들어 행을 기준으로 이 작업을 실시한다면, 1번 행에서는 빈칸이 있는 열을 제외하고는 모두 말을 놓을 수 있기에 1이라는 숫자를 넘버링 해주면 된다.

유사 문제로 아래의 두 문제가 있는데, 이 문제가 다른 룩 시리즈 문제와 다른 점은 보드 위에 벽이 존재하지 않고 단지 룩을 놓을 수 없는 빈칸만 있다는 것이다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import sys
input = sys.stdin.readline

r, c, n = map(int, input().split())

board = [[1] * c for _ in range(r)]
for i in range(n):
    x, y = map(int, input().split())
    board[x-1][y-1] = 0
    
    
ref = [[0] * c for _ in range(r)]
ref2 = [[0] * c for _ in range(r)]

# 행 기준으로 숫자를 매긴다. 즉 각각의 열이 어떤 행과 매칭한지 그룹을 구성하는 것이다. 
# 만약 1번 행에서 2, 3, 4번 열에 1이라는 숫자를 매긴다면, 이는 곧 이분 매칭할 때 2, 3, 4번 열 정점이 1번 행 정점과 매칭 가능하다는 것이다.
num = 1    
for i in range(r):
    for j in range(c):
        ref[i][j] = num
    
    num += 1    

# 여기서 일단 이분 매칭을 위한 edge 배열을 구성한다. 행 기준으로 숫자를 매긴 후의 num 값으로 배열을 만들기 때문이다. 
# 왜냐하면 나중에 열 정점을 기준으로 행 정점에 매칭시키기 때문이다.    
edge = [[] for _ in range(num)]
num = 1 # 변수 num 값 초기화 후 열 기준으로 숫자를 매긴다.    
for j in range(c):
    for i in range(r):
        ref2[i][j] = num
    
    num += 1    
    

# 열 정점을 기준으로 매칭시킬 수 있는 후보 행에 관한 정보를 넣는다.    
for i in range(r):
    for j in range(c):
        if board[i][j]:
            edge[ref[i][j]].append(ref2[i][j])
            
             
            
target = [0] * num
def sol(x):
    if visited[x]:
        return False
    
    visited[x] = 1
    for i in edge[x]:
        if not target[i] or sol(target[i]):
            target[i] = x
            return True
       
    return False

# 정점을 직접 만들었으니 len(edge) 값 사용.
count = 0
for i in range(1, len(edge)):
    visited = [0] * len(edge)
    if sol(i):
        count += 1
        
        
print(count)