백준 1799번 비숍 (알고리즘은 Chess(?))

문제

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

 

요약

이 문제는 백트래킹 문제인데, 매개변수 k를 어떻게 설정할지 고민하면서 시간을 정말 많이 썼다. 결국 다른 분의 기술 블로그에 나온 코드를 이해하여 완전히 이해하는 것을 목표로 잡고 풀게 되었다. (https://rapun7el.tistory.com/60) 일단 내 코드에서는 체스판 위의 공간을 어두운 부분과 밝은 부분, 두 부분으로 나누어서 아예 독립적으로 두고 각 부분에 놓을 수 있는 최대 비숍의 개수를 구한 뒤, 이 둘을 더해주는 방식으로 전개된다. 그리고 black, white 함수는 각각 backtracking 알고리즘으로 동작하며 비숍을 선택하는 모든 경우를 찾아 최대 비숍 개수를 계속 갱신해준다. 여기서 함수의 매개변수(흔히 백트래킹에서 k로 두는 값)는 nxn의 체스판을 우측으로 45도 회전했을 때의 행(row) 번호이다. 쉽게 말하면 체스판을 45도 회전하면 다이아몬드 형태가 되는데, 이때 각 행은 제일 가운데가 원소의 개수가 가장 많으며, 위 혹은 아래로 갈수록 행 위에 놓인 원소의 개수는 점점 줄어드는 구조인 것인데 매개변수는 행 번호가 된다. 백트래킹은 기본적으로 재귀적으로 각 단계에서 선택할 수 있는 값을 바꿔주며 모든 경우의 수를 탐색하여 k가 종착값에 다다르면 관심 있는 값을 업데이트해주는 알고리즘이다. 백트래킹 알고리즘으로 동작하는 black, white 함수는 각 행별로 원소 하나만 선택하는데(이렇게 하면 자연스럽게 우상향 대각선(↗) 상에서 다른 비숍에게 잡힐 일은 없게 된다.) 이때 원소가 우하향 대각선(↘)에 다른 비숍이 존재하지 않는다는 조건을 충족할 때 원소를 선택한다. 이렇게 하면 해당 원소를 포함한 두 대각선 상에서 다른 비숍에서 잡힐 일이 없게 되는 것이다.

 

코드

import sys
input = sys.stdin.readline

# input
N = int(input())
chess = []
for _ in range(N):
    row = list(map(int, input().split()))   
    chess.append(row)

# solution

def white(N, chess, white_leftdiag, n, cnt):
    global white_cnt
    if n == N:
        white_cnt = max(white_cnt, cnt)
        return
    flag = 1
    for i in range(-N//2, N//2+1):
        if (0<=n+i<N and 0<=n-i<N):
            if chess[n+i][n-i]:
                if white_leftdiag[i]:
                    continue
                white_leftdiag[i] = 1
                flag = 0
                white(N, chess, white_leftdiag, n+1, cnt+1)
                white_leftdiag[i] = 0
    if flag: white(N, chess, white_leftdiag, n+1, cnt)
    
def black(N, chess, black_leftdiag, n, cnt):
    global black_cnt
    if n == N:
        black_cnt = max(black_cnt, cnt)
        return
    flag = 1
    for i in range(-N//2, N//2):
        if (0<=n+1+i<N and 0<=n-i<N):
            if chess[n+1+i][n-i]:
                if black_leftdiag[i]:
                    continue
                black_leftdiag[i] = 1
                flag = 0
                black(N, chess, black_leftdiag, n+1, cnt+1)
                black_leftdiag[i] = 0
    if flag: black(N, chess, black_leftdiag, n+1, cnt)
    
def solution(N, chess):
    global white_cnt, black_cnt
    white_cnt = 0
    black_cnt = 0
    white_leftdiag = {i:0 for i in range(-N//2, N//2+1)}
    black_leftdiag = {i:0 for i in range(-N//2, N//2)}
    white(N, chess, white_leftdiag, 0, 0)
    black(N, chess, black_leftdiag, 0, 0)
    return white_cnt + black_cnt

print(solution(N, chess))

 

Trouble Shooting : 다른 함수에서 선언된 int 값을 수정하고 싶을 때는?

곧 있을 코딩테스트가 진행되는 프로그래머스 환경에서 문제를 푸는 연습을 하고자, solution 함수 내부에서 변수를 선언해주는 연습을 해봤다. solution 함수에서 선언된 white_cnt 변수의 값을 white 함수에서 수정하고자 할 때 처음에는 사용하는 함수(white 함수)에서만 global이라고 명시해두면 되는 줄 알았다. white 함수에 global white_cnt 라고 코드를 추가해도 전역변수로 처리되지 않자 당황했다. 그래서 처음에 선택한 것은 immutable인 int 변수를 mutable인 리스트 변수로 탈바꿈하는 것이었다. 그래서 [(기존의 white_cnt로 썼던 int 값)]처럼 리스트를 매개변수로 넘겨주어 Call by Reference를 시도했고, 값 수정에 성공했다. 그런데 변수가 처음 선언된 곳과 변수를 참조할 곳 모두에서 global로 선언하면 된다는 것을 뒤늦게 깨달았다......!!