(Python/🥇3)백준알고리즘 30242번: N-Queen(Easy)

문제 바로가기 

 

 

풀이:

 

원래 N-Queen 문제랑 비슷한대 미리 지정된 queen들만 생각해두면 된다하여 쉽다고 생각했다.

 

그래서 lst를 돌면서 만약 퀸이 이미 있는 상태면 다음으로 넘겨주는 식으로 하였고

시간초과가 나서 이미 숫자가 있는것은 빼줬지만 그것마저 시간초과가 났다.

 

틀린 풀이:

import sys

n = int(input())
# lst = [0] * n
lst = list(map(int,sys.stdin.readline().rstrip().split()))
numbers = sorted(list(set([i for i in range(n+1)]) - set(lst)))
def is_possible(x):
    for i in range(x):
        if lst[i] == lst[x] or abs(x-i) == abs(lst[x]-lst[i]):
            return False
    return True


def bt(i):
    global res
    if i == n:
        print(*lst)
        exit()
    # 이미 퀸이 두어져 있을경우
    if lst[i] != 0:
        # 그전 까지 둔거랑 확인
        if is_possible(i):
            # 근데 가능함, 그럼 다음꺼 두러
            bt(i+1)
        #     안되면 돌아감
        return
    # 퀸이 배치가 안됨
    for j in numbers:
        # 퀸 두기
        lst[i] = j
        # 가능성체크
        if is_possible(i):
            # 가능하면 다음꺼 두러감
            bt(i+1)
        # 돌려 두기
        lst[i] = 0
bt(0)
print(-1)

 

 

이 방법은 되지 않아 

대각선 체크하는게 매번 체크를 하기때문에 문제가 된다.

그럼 대각선 체크를 포문으로 안 하고  하면 된다.

각 점마다 위로대각선 아래로 대각선으로 해서 가장 끝 자리에 도착했을때 그게 안 겹치면 된다.

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

# 시간 초과
# 1. 탐색하는 Numbers에 숫자를 이미 배치된 숫자를 빼고 함 -> 50%
# 2. is_possibe 을 자주 호출함

n = int(input())
lst = list(map(int, sys.stdin.readline().split()))

# 가로 체크
col = [False] * (n + 1)
up = [False] * (2 * n)
down = [False] * (2 * n)
nums = sorted(set(range(1, n + 1)) - set(lst))

def bt(i):
    if i == n:
        print(*lst)
        exit()
    if lst[i]:  # 이미 퀸이 놓인 경우
        if not (col[lst[i]] or up [i-lst[i] +n ] or down[i + lst[i]]):
            col[lst[i]] = up[i-lst[i] +n ] = down[i + lst[i]] = True
            bt(i+1)
            col[lst[i]] = up[i-lst[i] +n ] = down[i + lst[i]] = False
        return

    for j in nums:  # 퀸 둬야함
        if not (col[j] or up[i - j + n] or down[i + j]):
            lst[i] = j
            col[j] = up[i - j + n] = down[i + j] = True
            bt(i + 1)
            col[j] = up[i - j + n] = down[i + j] = False
            lst[i] = 0

bt(0)
print(-1)