[백준 1799번] 파이썬 - 비숍

백준 1799_비숍

시간 제한 10초, 메모리 제한 128MB

# 조건

• 서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다.
• < 그림 1 >과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다.

![[Algorithm/baekjoon_python/assets/Pasted image 20230430173854.png]]

• 그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다.
• < 그림 2 >에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 < 그림 3 >과 같이 최대 7개의 비숍을 놓을 수 있다.
• 색칠된 부분에는 비숍이 놓일 수 없지만 지나갈 수는 있다.

![[Algorithm/baekjoon_python/assets/Pasted image 20230430173914.png]]

• 정사각형 체스판의 한 변에 놓인 칸의 개수를 체스판의 크기라고 한다.
• 체스판의 크기와 체스판 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 주어질 때, 서로가 서로를 잡을 수 없는 위치에 놓을 수 있는 비숍의 최대 개수를 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 체스판의 크기가 주어진다.
• 체스판의 크기는 10이하의 자연수이다.
• 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 한 줄씩 주어진다.
  • 비숍을 놓을 수 있는 곳에는 1, 비숍을 놓을 수 없는 곳에는 0이 빈칸을 사이에 두고 주어진다.

출력

• 첫째 줄에 주어진 체스판 위에 놓을 수 있는 비숍의 최대 개수를 출력한다.

# 접근 방법

• 모든 경우를 백트래킹으로 돌리게 되면, O(2^100)의 시간복잡도가 발생한다.
• 따라서, 우상향 대각선과 우하향 좌선으로 생각해준다.
  • 우상향 좌선의 경우 i+j의 값이 일정하고
  • 우하향 좌선의 경우 i-j의 값이 일정하다.

• 해당 대각선을 위에서부터 0,1,2... 번호를 매겨준다.
  • 우상향 대각선을 기준으로 해당 번호를 인덱스 번호로 사용하여
  • 각 대각선마다 비숍을 넣을 수 있는 칸을 기록해준다.
  • 사선의 번호는 0 ~ 2 * N - 1 까지 나올 수 있다.
  • ex) 0번 대각선 [0,0], 1번 대각선 [0,1] => [[(0,0)], [(0,1)] ... ]
• 0번 인덱스부터 1번, 2번 .. 2 * N -1 개를 가지치기 해주며 백트래킹을 실행해준다.

• dfs를 돌리며 인자는 선택된 대각선 번호 k과, 현재 놓여진 체스말 cnt를 넘겨준다.
• 백트래킹을 위하여 최상단에 가지치기를 해준다.
  • 남은 자리를 다 놓아도 ans보다 작은 경우 return
  • 종료 조건은 k == 2 * L - 1 인 경우 cnt를 return 해준다.
• 이 경우, 같은 우상향 대각선에 위치한 비숍은 하나씩 돌므로 확인 해 줄 필요없다.
  • 따라서 ci - cj 의 칸 => 우하향 대각선만 체크 해주면 된다.
  • visited 배열을 2 * L - 1 크기로 만들어 준 후, 해당 우하향 대각선 위치 (ci-cj) 에 비숍이 놓였는지 체크해주면 된다.
• 안 놓고 가는 경우도 체크해주면 되는데 cnt를 그대로 넘겨주는 차이만 있다.

n-queen과 비슷하였지만, 시간을 줄이는데 있어서 조금 힘들었다.
또한, 위 코드에서 서로 영향을 줄 수 없는 칸을 나누거나,
이분 매칭을 이용하여 풀 수도 있는데 아래 유튜브와 블로그를 참고하면 이해하는데 도움이 될 것 같다!!

• https://www.youtube.com/watch?v=Op0dtMMyeyg
• https://blog.naver.com/kks227/220807541506

백트래킹 이용

import sys  
sys.stdin = open('input.txt')  


def dfs(k, cnt):  
    global ans  
    # 가지치기  
    # 남은 위치를 다 놓아도 작은 경우  
    if ans >= (cnt+L-k):  
        return  
    if k == L:  
        ans = max(ans, cnt)  
        return  

    # 현재 대각선번호에서 가능한 위치 하나씩 놓고 다음 대각선으로 가기  
    for ci, cj in lst[k]:  
        if visited[ci-cj] == 0:  
            visited[ci-cj] = 1  
            dfs(k+1, cnt+1)  
            visited[ci-cj] = 0  
    # 이번 대각선에서 안놓고 다음으로 넘어가기  
    dfs(k+1, cnt)  

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

lst = [[] for _ in range(2*n-1)]  

# arr[i][j] == 1 인 경우 i+j 위치에 appendfor i in range(n):  
    for j in range(n):  
        if arr[i][j] == 1:  
            lst[i+j].append((i, j))  

L = 2 * n - 1  
visited = [0] * L  

ans = 0  
dfs(0, 0)  
print(ans)

위 코드 다듬기

• 위와 같이 흰 칸과 검은 칸으로 나눠서 생각주면 된다.
• 이 때, 서로 다른 색의 칸들은 상호독립적이므로 위의 코드에서 조금만 고쳐주면 된다.
• 검은 칸의 경우 0부터 2씩 증가
• 흰 칸의 경우 1부터 2씩 증가하며
  • 가지치기 남은 칸의 경우 // 2 를 통하여 줄여주면 된다.

import sys  
sys.stdin = open('input.txt')  


def dfs(k, cnt):  
    global ans  
    # 가지치기  
    # 남은 위치를 다 놓아도 작은 경우  
    # 2개씩 건너뛰므로 // 2    if ans >= (cnt+(L+1-k)//2):  
        return  
    if k >= L:  
        ans = max(ans, cnt)  
        return  

    # 현재 대각선번호에서 가능한 위치 하나씩 놓고 다음 대각선으로 가기  
    for ci, cj in lst[k]:  
        if visited[ci-cj] == 0:  
            visited[ci-cj] = 1  
            dfs(k+2, cnt+1)  
            visited[ci-cj] = 0  
    # 이번 대각선에서 안놓고 다음으로 넘어가기  
    dfs(k+2, cnt)  

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

lst = [[] for _ in range(2*n-1)]  

# arr[i][j] == 1 인 경우 i+j 위치에 appendfor i in range(n):  
    for j in range(n):  
        if arr[i][j] == 1:  
            lst[i+j].append((i, j))  

L = 2 * n - 1  
visited = [0] * L  

# 체스판의 흑/백은 비숍이 상호간 이동 불가하다.  
# 0 부터 시작해서 2씩 증가 + 1부터 시작해서 2씩 증가  
ans = 0  
# 0부터 2씩 증가  
dfs(0, 0)  
t = ans  
ans = 0  
# 1부터 2씩 증가  
dfs(1, 0)  
print(ans+t)

 

• 시간 차이가 어마어마하다...