백준 9525 룩 배치하기

작성일 | In |

문제 링크

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

알고리즘

  • 이분 매칭

풀이

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

차이점은 이번 문제의 경우 체스판 위에 빈칸이 있는 게 아니라 폰(벽이라고 생각하면 된다.)이 있기 때문에 룩이 이동할 수 있는 공간제약이 있다는 것이다.

따라서 같은 행이나 열에 룩이 이미 존재하더라도 사이에 폰이 존재하게 되는 상황이라면 또 다른 룩을 놓을 수 있다는 걸 생각하면 된다.

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

전체 코드

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
82
83
84
import sys
input = sys.stdin.readline

n = int(input())

board = []
for i in range(n):
    board.append(list(input().strip()))
    

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


num = 1    
for i in range(n):
    check = False
    for j in range(n):
        if board[i][j] == '.':
            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(n):
    check = False
    for i in range(n):
        if board[i][j] == '.':
            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(n):
        if ref[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 not target[i] 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)