글 읽기 - python 시간초과 부탁드립니다

lesk012 2년 전 0

시간 복잡도가 높은데 어떤 식으로 개선해야 할 지 감이 안 잡혀서 질문 드립니다

힌트 주시면 감사드리겠습니다 !

import sys

n = int(sys.stdin.readline())
chess = [[0]*n for i in range(n)]
result = 0

def check_pos(row, col, chess):
    for r in range(n):
        if chess[r][col] == 1:
            return False
        for c in range(n):
            if (abs(row-r) == abs(col-c)) and chess[r][c] == 1:
                return False
    return True

def queen(row, chess):
    global result

    if row == n:
        result += 1
        return

    for col in range(n):
        if check_pos(row, col, chess):
            chess[row][col] = 1
            queen(row+1, chess)
            chess[row][col] = 0

queen(0, chess)
print(result)

lesk012 2년 전 0

네 여전히 시간초과네요

lesk012 2년 전 0

의견 감사합니다

반영해서 수정해봤는데, 그래도 시간 초과네요 ㅠ

여유 있으실 때 코드 한번 봐주시겠어요?

감사합니다 !!

import sys

n = int(sys.stdin.readline())
chess = set()
result = 0

def check_pos(row, col, chess):
    if len(chess) == 0:
        return True
    for r, c in chess:
        if col == c:
            return False
        elif abs(row-r) == abs(col-c):
            return False
    return True

def queen(row, chess):
    global result
    if row == n:
        result += 1
        return
    for col in range(n):
        if check_pos(row, col, chess):
            chess.add((row, col))
            queen(row+1, chess)
            chess.remove((row, col))

queen(0, chess)
print(result)

shinryan9 2년 전 0

check_pos함수의 elif abs(row-r) == abs(col-c):부분에서 row-r를 절대값으로 할 이유가 있나요? queen함수에 넣어 줄때 row+1을 하므로 필요 없지 않을까요?

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

python 시간초과 부탁드립니다

lesk012 2년 전 0

lesk012 2년 전 0

lesk012 2년 전 0

shinryan9 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말