글 읽기 - 파이썬 1%에서 터지는데 왜그런지 모르겠습니다....

ghks2047 2년 전 0

백트래킹으로 구현했습니다.

예제도 잘되고 전부 0값으로 만들어서 풀어도 잘 되는거 확인했습니다.

실패한 경우 이전 값을 0으로 다시 만들어 주는 것도 했구요.

그런데 1%에서 자꾸 실패하니 어떤게 문제인지 잘 모르겠네요.

empty = []
board = []
for i in range(9):
    tmp = list(map(int, input().split()))
    for j in range(9):
        if tmp[j] == 0:
            empty.append((i, j))
    board.append(tmp)


def check(i, j, val):
    # side중복 있는지
    for z in range(9):
        if j != z and board[i][z] == val:
            return False
        # topdown중복 있는지
        if i != z and board[z][j] == val:
            return False
    # 3x3중복 있는지
    ri = i//3
    rj = j//3
    for y in range(ri*3, ri*3+3):
        for x in range(rj*3, rj*3+3):
            if [y, x] != [i, j] and board[y][x] == val:
                return False
    return True


def backTracking(order, oi, val):
    if len(order) == oi:
        for _ in board:
            print(" ".join(map(str, _)))
        return True
    i, j = order[oi]
    board[i][j] = val
    # 검토 안되면 return false
    if check(i, j, val) == False:
        board[i][j] = 0
        return False

    i, j = order[oi]
    for z in range(1, 10):
        if backTracking(order, oi+1, z) == True:
            return True
    return False


for i in range(1, 10):
    if backTracking(empty, 0, i) == True:
        break

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

문제

문제

출처

ICPC

파이썬 1%에서 터지는데 왜그런지 모르겠습니다....

ghks2047 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말