글 읽기 - [파이썬] 출력초과는 어디서 나는걸까요? ㅠㅠ

gyjinro 2년 전 1

백트레킹이라고 열심히 만들어서 돌려 봤더니, 출력초과가 나옵니다.

시간 초과라면 이해가 가지만서도.. 출력초과는 어떤게 잘 못 되서 나오는지 몰라서 질문을 올립니다.

고수님들 말씀 부탁드립니다. ㅠㅠ

import sys
input = sys.stdin.readline
b_dict = {(0, 0): [False] * 10,
          (0, 1): [False] * 10,
          (0, 2): [False] * 10,
          (1, 0): [False] * 10,
          (1, 1): [False] * 10,
          (1, 2): [False] * 10,
          (2, 0): [False] * 10,
          (2, 1): [False] * 10,
          (2, 2): [False] * 10}
row = [[False] * 10 for _ in range(10)]
col = [[False] * 10 for _ in range(10)]
board = []
for i in range(9):
    line = input().rstrip()
    for j in range(9):
        n = int(line[j])
        board.append(n)
        b_dict[(i//3, j//3)][n] = True
        row[i][n] = True
        col[j][n] = True


def sudoku(num, board):
    if num == 81:
        res = list(map(str, board))
        for l in range(9):
            print("".join(res[l * 9:l * 9 + 9]))
    elif board[num]:
        sudoku(num + 1, board)
        return
    else:
        i = num // 9
        j = num % 9
        for k in range(1, 10):
            if not b_dict[(i//3, j//3)][k] and not row[i][k] and not col[j][k]:
                b_dict[(i//3, j//3)][k] = True
                row[i][k] = True
                col[j][k] = True
                board[num] = k
                sudoku(num+1, board)
                b_dict[(i//3, j//3)][k] = False
                row[i][k] = False
                col[j][k] = False
                board[num] = 0
        return


sudoku(0, board)

dps2 2년 전 3

출력을 읽어보시면

9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

라고 되어있는데 아래 케이스를 넣으면 출력이 여러번 됩니다

000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000

gyjinro 2년 전 0

감사합니다!

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

문제

문제

출처

ICPC

[파이썬] 출력초과는 어디서 나는걸까요? ㅠㅠ

gyjinro 2년 전 1

dps2 2년 전 3

gyjinro 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말