[BOJ] 1799 비숍

 

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

 

주어진 체스판 위에서 비숍을 최대 몇 개까지 둘 수 있는지 세는 문제.

 

 

1/ 조건

1) 입력 첫 줄에는 정사각형 체스판의 크기 n이 주어진다. 1 <= n <= 10.

2) n*n 행렬이 주어진다. 각 원소가 1이면 해당 위치에는 비숍을 둘 수 있고, 0이라면 둘 수 없다.

 

 

2/ 설계

당연하게도 바로 DFS를 썼다. 정확히는 백트래킹. 가지치기를 생각할 수 있는 데까지 해봤지만 n=10에서 모든 칸에 비숍을 둘 수 있는 경우를 해결하긴 어려웠다.

나는 'n이 정해지면 비숍의 최대치가 정해지는가?'라는 질문에 대해 생각했다. 답은 2n-2. 엄밀한 증명을 통해 얻어낸 것은 아니지만 확신은 있었다.

대략적인 추론 과정은 이렇다. n*n 행렬에 존재할 수 있는 대각선은 2n-1개다. 행렬을 45도 회전시키면 그 사실을 쉽게 확인할 수 있다.

그러니까, n*n보드를 45도 돌려서 (2n-1)*(2n-1) 보드 위로 이식했다. 그러면 문제는 비숍이 아니라 룩의 문제로 환원되고, 경로를 1차원으로 기술할 수 있게 된다. 이러면 연산이 확실하게 줄어들 거라고 판단했다.

 

 

3/ 구현

def dfs(lvl, cnt, path):
    global max_cnt

    if cnt + (l - lvl) <= max_cnt:
        return

    if lvl == l:
        max_cnt = max(max_cnt, cnt)
        return

    for i in range(l):
        if degree45[lvl][i] and not (path & (1 << i)):
            dfs(lvl+1, cnt+1, path | (1 << i))	    # 그 행에서 룩을 고르는 경우
    dfs(lvl+1, cnt, path)                           # 그 행에서 룩을 고르지 않고 넘어가는 경우


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

# 회전
l = 2*n - 1
degree45 = [[0]*l for _ in range(l)]
for i in range(n):
    for j in range(n):
        degree45[i+j][n-1-i+j] = board[i][j]

max_cnt = 0
dfs(0, 0, 0)

print(max_cnt)

 

비트마스킹을 배운 지 얼마 안 돼서 꾸역꾸역 써봤다.

 

 

4/ 결과

야호!

 

 

5/ 후기

1) 요즘 문제 풀이에 소홀했다. 체력도 체력이고 우선순위가 낮게 느껴져서. 그래서 매번 딱 보고 알 것 같은 문제만 풀다가 힘을 내서 골드1 문제에 도전해봤다. 90분 정도 가지치기에 열을 올리다가 회전시키는 아이디어가 떠올랐고, 집에 돌아와서 풀었다. 코드 길이도 연산도 짧아지고 아이디어 자체도 (내겐) 매력적이라서 마음에 들었다.

2) 다른 사람들 풀이를 보니까 풀이가 Python3로 40ms에 풀리는 풀이가 있는 듯했다. 대체 어떤 경이로운 풀이인가 했는데 이분 매칭(bipartite matching)이라는 듯하다. 모레 즈음에 들여다 볼 생각이다.

3) 뭔가 DP로 풀릴 듯 말 듯한 기분이라 묘하다. 메모이제이션은 가능하지만 최선의 상태를 규정할 수 없기에 DP는 안 된다는 게 지금의 결론이다. DP도 좀 더 알아두고 싶은데.

4) CP를 할 게 아니라면 알고리즘 문제 해결을 깊이 공부하는 데 의미가 있을까? 있다면 어떤 의미일까? 고민해볼 만한 거리인 것 같다.