백준 1799번 비숍

문제 설명

 

 

 

N-Queen 문제를 돌려서 생각하여 (왼쪽에서 오른쪽으로 가는) / 모양의 대각선으로 해당 줄을 검사하면서 한 줄 씩 내려갔다. 훑어야 하는 대각선의 총 개수는 체스판의 크기 * 2 - 1 이다. (예를 들어, 체스판 크기가 3이면 ///// 이렇게 5개를 검사해야한다.) / 대각선을 N-Queen의 가로라고 보면 된다. isused는 ＼모양의 대각선으로 

이런 식으로 (x,y)에 비숍을 넣으면 isused(x-y+체스판 크기-1)의 값을 1로 설정하여 해당 대각선은 사용되고 있다는 것을 표시해줬다.

 

함수의 매개변수로 cur, length, count를 설정했는데 cur은 현재 / 대각선의 위치(체스판 크기가 3이면 0부터 5까지다.), length는 / 대각선이 체크할 체스판의 개수, count는 현재 비숍의 개수다. cur == 체스판 크기 * 2 - 1 이면 마지막 대각선 다음이므로 비숍의 최대 개수를 변경해준다.

 

 

cur < num - 1일 경우는 / 대각선이 체스판을 / 방향으로 반으로 나누었을 때 윗부분을 뜻한다.

no_place는 비숍을 놓을 위치가 있는지 구분하기 위한 flag고 true면 놓을 곳이 없는 것이고 false면 놓을 수 있는 곳이 있다는 것이다. for문의 i는 / 대각선의 열을 뜻하고 cur_x와 cur_y는 현재 체스판의 위치값을 계산한 것이다. isused값이 1이면 해당 ＼대각선에 비숍이 있으므로 continue를 하고 isused값이 0이면 비숍이 없으므로 해당 위치에 비숍을 놓을 수 있는지 확인한다. 놓을 수 있는 경우 isused값을 1로 변경한 후 다음 / 대각선으로 넘어간다.

 

 

이렇게 밑부분의 체스판에도 똑같이 적용한다.

 

 

전체 코드

arr = []
isused = []
num = 0
max_count = 0

def func(cur,length,count):
    global num
    global max_count
    if cur == num*2-1:
        if count > max_count:
            max_count = count
        return

    if cur < num-1:
        no_place = True
        for i in range(length):
            cur_x = cur - i
            cur_y = i
            if isused[cur_x-cur_y+num-1]:
                continue
            if arr[cur_x][cur_y]:
                isused[cur_x-cur_y+num-1] = 1
                func(cur+1,length+1,count+1)
                isused[cur_x-cur_y+num-1] = 0
                no_place = False
        if no_place:
            func(cur + 1, length + 1, count)

    else:
        x_pos = num-1
        y_pos = cur-x_pos
        no_place = True
        for i in range(length):
            cur_x = x_pos-i
            cur_y = y_pos+i
            if isused[cur_x-cur_y+num-1]:
                continue
            if arr[cur_x][cur_y]:
                isused[cur_x-cur_y+num-1] = 1
                func(cur+1,length-1,count+1)
                isused[cur_x-cur_y+num-1] = 0
                no_place = False
        if no_place:
            func(cur + 1, length - 1, count)
    return

def main():
    global arr
    global num
    global isused
    num = int(input())
    arr = [list(map(int,input().split())) for _ in range(num)]
    isused = [0] * (num*2-1)
    func(0,1,0)
    print(max_count)
    return

if __name__ == "__main__":
    main()