백준 9663번: N-Queen

BOJ

백준 9663번: N-Queen

접근

Queen 가로, 세로, 대각선 어떤 방향이든 원하는 만큼 이동할 수 있다. 퀸이 놓였을 때 자신을 기준으로 같은 행과 열, 대각선에는 아무것도 놓여있으면 안 된다.

퀸을 다음 행에 둘 수 없을 때 이전 행으로 되돌아가기 때문에 백트래킹을 이용할 수 있다.

# A -> B 로 물을 옮길 때
water = min(x, B - y)
pour(x - water, y + water)

Correct Solution

import sys
from collections import deque
input = sys.stdin.readline

A, B, C = map(int, input().split())

def pour(x, y):
    if not visit[x][y]:
        visit[x][y] = True
        q.append([x, y])


def bfs():
    # bfs 시작!
    q.append([0, 0])
    visit[0][0] = True

    while q:
        x, y = q.popleft()
        z = C - x - y
        if x == 0:
            ans.append(z)

        # x -> y
        water = min(x, B - y)
        pour(x - water, y + water)

        # x -> z
        water = min(x, C - z)
        pour(x - water, y)

        # y -> x
        water = min(y, A - x)
        pour(x + water, y- water)

        # y -> z
        water = min(y, C - z)
        pour(x, y - water)

        # z -> x
        water = min(z, A - x)
        pour(x + water, y)

        # z -> y
        water = min(z, B - y)
        pour(x, y + water)


q = deque()
ans = []

visit = [[False] * (B + 1) for _ in range(A + 1)]
bfs()

ans.sort()
print(' '.join(map(str, ans)))

참고 사이트

[ChanBLOG]](https://chanhuiseok.github.io/posts/baek-1/)