[백준알고리즘] 1799번: 비숍 -Python

[백준알고리즘] 1799번: 비숍 -Python

https://www.acmicpc.net/problem/1799

1799번: 비숍

이 한문제를 푸는데 굉장히 오래 걸렸다. 처음에는 N-Queen 문제랑 비슷하다고 생각하며 너무 쉽게 생각했다.

N-Queen 문제와 비슷하기는 하지만 N-Queen은 한 행과 한 열에 하나씩 배치하기 때문에 배치할 공간이 훨씬 줄어들기 때문에 더 쉽게 풀 수 있던 것 같다.

 

이번 문제는 대각선만 생각해야 한다. 시간제한이 10초나 주어져있지만, 모든 점이 1일 경우 O(2^(N*N))의 시간이 걸리며, 이는 최대 2^100이기 때문에 시간이 부족하다.

 

그래서 푸는 방법을 찾아보고 풀게 되었다.

 

두 가지 방법으로 풀었는데, 첫 번째는 실제 체스판의 검정 칸과 흰 칸을 따로 생각하는 것이다. 이 방법은 N*N의 크기를 (N/2)*(N/2) * 2의 크기로 생각해서 푸는 것이기 때문에 시간 복잡도도 O(2^(N*N/4))가 된다. 이는 최대 2^25이며 이 또한 큰 값이지만 케이스를 나누지 않고 생각했던 것보다 엄청나게 줄어든 것을 확인할 수 있다.

 

그리고 한가지 점검을 해주지 않아 엄청 골머리를 앓았던 문제가 있다. 바로 n이 짝수일 때다.

리스트의 값을 idx하나로 행과 열을 인덱싱 하도록 해주었는데, idx+2씩 늘려가며 검정 칸 또는 흰 칸에 대해서 접근해주었다. n이 홀수일 때에는 다음과 같이 체스판이 격자로 잘 배치가 되는 반면에 n이 짝수인 경우에는 그렇지 않다.

 

n = 3

흑 백 흑

백 흑 백

흑 백 흑

-> [흑, 백, 흑, 백, 흑, 백, 흑, 백, 흑]

 

n = 2

흑 백

흑 백

-> [흑, 백, 흑, 백]

 

따라서 n이 짝수인 경우에는 한 칸씩 이동되어 칸이 구분되는 것을 생각해주어야 대각선 점검 시 적절히 수행될 수 있다.

def check(idx):
    c = idx%2
    i, j = idx//n, idx%n

    for d in range(4):
        x, y = i+dx[d], j+dy[d]
        while 0<=x<n and 0<=y<n:
            if visited[x*n + y]:
                return False
            x += dx[d]
            y += dy[d]
    return True

def dfs(idx, c, cnt):
    if n*n-idx+1+cnt <= ans[c] or idx >= n*n: 
        return

    ans[c] = max(ans[c], cnt)
    x, y = idx//n, idx%n
    j = y
    for i in range(x, n):
        while j < n:
            v = i*n + j
            if not visited[v] and chess[i][j] == 1 and check(v):
                visited[v] = True
                dfs(v, c, cnt+1)
                visited[v] = False
            j += 2
        j = (c+1)%2 if i%2 == 0 else c

n = int(input())
chess = [list(map(int, input().split())) for _ in range(n)]
dx, dy = [1, -1, 1, -1], [1, 1, -1, -1]
visited = [False] * (n**2)
ans = [0, 0]

# 짝수는 0, 홀수는 1
dfs(0, 0, 0)
dfs(1, 1, 0)
print(sum(ans))

 

두 번째 방법은 이분 매칭을 이용한 풀이이다.

이분 매칭의 알고리즘에 대해서는 라이님의 블로그를 통해 이해하게 되었다.

그리고 해당 문제의 @hello70825 님의 코드도 많이 도움이 됐다.

 

먼저 말하지만 이분 매칭을 사용한 코드의 경우 속도가 매우 빨랐다... 파이썬 제출된 시간들을 보면 긴건 위의 방식, 짧은건 이 이분 매칭 방식으로 봐도 된다.

 

그리고 이분 매칭을 구현할 때 DFS로 구현하는 것이 간단하면서도 효율적이라고 한다. 하지만 최대로 효율을 내는 알고리즘은 따로 있는듯하다. 

 

이분 매칭을 위해 우선은 두 그룹으로 나눠야 한다. 비숍을 둘 때 같은 대각선에 위치하면 안 되기 때문에 대각선에 넘버링을 해준다. 이때 ↘와 ↙ 방향의 대각선들로 넘버링을 각각 해주어 두 가지 그룹을 만들었다.

 

그 후 비숍을 놓을 수 있는 자리에서 두 대각선이 만나는 지점을 link라는 리스트로 기록해주었다. 하나의 그룹의 대각선 넘버가 인덱스 번호이며, 다른 하나의 그룹의 대각선 넘버가 값을 갖도록 했다.

 

이후 왼쪽 그룹에서 오른쪽 그룹으로 매칭이 가능한 경우를 dfs()를 통해 검사하면서 이분 매칭 해주었다.

n = int(input())
table = [list(map(int, input().split())) for _ in range(n)]
right = [[0] * n for _ in range(n)]
left = [[0] * n for _ in range(n)]
r, l = 1, 1

for j in range(n):
    i = 0
    while i<n and 0<=j:
        if table[i][j] == 1:
            right[i][j] = r
        i += 1; j -= 1
    r += 1
for i in range(1, n):
    j = n-1
    while i<n and 0<=j:
        if table[i][j] == 1:
            right[i][j] = r
        i += 1; j -= 1
    r += 1

for j in range(n-1, -1, -1):
    i = 0
    while i<n and j<n:
        if table[i][j] == 1:
            left[i][j] = l
        i += 1; j += 1
    l += 1
for i in range(1, n):
    j = 0
    while i<n and j<n:
        if table[i][j] == 1:
            left[i][j] = l
        i += 1; j += 1
    l += 1

# 1<= l, r <=2*n
link = [[] for _ in range(l)]
for i in range(n):
    for j in range(n):
        if table[i][j]:
            link[left[i][j]].append(right[i][j])

def dfs(idx):
    visited[idx] = True
    l = link[idx]
    for p in l:
        if r2l[p] == 0 or (not visited[r2l[p]] and dfs(r2l[p])):
            r2l[p] = idx
            l2r[idx] = p
            return True
    return False

l2r = [0] * (2*n)
r2l = [0] * (2*n)
ans = 0
for i in range(1, 2*n):
    visited = [False] * (2*n)
    if dfs(i):
        ans += 1
print(ans)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다