백준 1760 N-Rook

작성일 | In |

문제 링크

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

알고리즘

  • 이분 매칭

풀이

지난번에 설명한 ‘룩 어택’과 비슷한 문제다.

이번 문제는 ‘룩 어택’이나 ‘룩 배치하기’보다 어렵다. 체스판 위에 구덩이와 벽이 동시에 존재하기 때문이다.

구덩이가 있는 곳에는 룩을 놓을 수 없고, 벽을 룩이 이동할 수 없기 때문에 벽을 사이에 두고 같은 행이나 열에 또 다른 룩이 있을 수 있다.

이 문제를 푼다면 룩 배치하기, 게시판 구멍 막기, 룩 어택은 쉽게 풀 수 있을 것이다.

코드에 대한 설명은 지난 게시물에 적어놨으니 이번엔 생략…!

전체 코드

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
import sys
input = sys.stdin.readline

n, m = map(int, input().split())

board = []
for i in range(n):
    board.append(list(map(int, input().split())))
    

ref = [[0] * m for _ in range(n)]
ref2 = [[0] * m for _ in range(n)]


num = 1    
for i in range(n):
    check = False
    for j in range(m):
        if board[i][j] == 0 or board[i][j] == 1:
            ref[i][j] = num
            check = True
        
        else:
            if check:
                num += 1
                check = False
    
    if check:
        num += 1    
        
        

edge = [[] for _ in range(num)]

num = 1    
for j in range(m):
    check = False
    for i in range(n):
        if board[i][j] == 0 or board[i][j] == 1:
            ref2[i][j] = num
            check = True
        
        else:
            if check:
                num += 1
                check = False
                
       
    if check:
        num += 1
    

for i in range(n):
    for j in range(m):
        if board[i][j] == 0:
            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 target[i] == 0 or sol(target[i]):
            target[i] = x
            return True
        
    return False


count = 0
for i in range(1, len(edge)):
    visited = [0] * len(edge)
    if sol(i):
        count += 1
        
print(count)