백준 2580 스도쿠

gmlwlswldbs·2022년 2월 26일
0

코딩테스트

목록 보기
128/130
import sys
input = sys.stdin.readline

g = [list(map(int, input().split())) for _ in range(9)]

# 공백을 구함
blank = []
for i in range(9):
    for j in range(9):
        if g[i][j] == 0:
            blank.append((i, j))

# 모든 공백에 대해 들어갈 수 있는 수를 구함
poss = [[] for _ in range(len(blank))]
for u in range(len(blank)):
    x, y = blank[u]
    # 집합에 1부터 9까지 담아줌
    update = set(i for i in range(1, 10))
    # 가로 탐색
    # 같은 행에 있는 숫자들은 못들어가니까 빼줌
    r_set = set(g[x])
    update = update - r_set
    # 세로 탐색
    # 같은 열에 있는 숫자들은 못 들어가니까 빼줌
    tmp = set()
    for i in range(9):
        if g[i][y] != 0:
            tmp.add(g[i][y])
    update = update - tmp
    # 정사각형 탐색
    # 같은 정사각형에 있는 숫자들은 못 들어가니까 빼줌
    tmp = set()
    nu, nv = x//3 * 3, y//3 * 3
    for row in [nu, nu+1, nu+2]:
        for column in [nv, nv+1, nv+2]:
            if g[row][column] != 0:
                tmp.add(g[row][column])
    update = update - tmp
    poss[u] = list(update)

# 그 자리에 들어갈 수 있는지 확인
def check(x, y, g):
    for i in range(9):
        if g[i][y] == g[x][y] and i != x:
            return 0
    for i in range(9):
        if g[x][y] == g[x][i] and i != y:
            return 0
    nu, nv = x//3 * 3, y//3 * 3
    for row in [nu, nu+1, nu+2]:
        for column in [nv, nv+1, nv+2]:
            if g[row][column] == g[x][y] and (row, column) != (x, y):
                return 0
    return 1

# 칸마다 가능한 숫자를 넣어서 정답을 구한다
def go(i, g, x, y):
    if i != 0 and check(x, y, g) == 0:
        return
    if i == len(blank):
        for r in range(9):
            print(*g[r])
        # 답이 여러 개인 경우 하나만 출력하기 위해 return 대신 exit  
        exit(0) 
    x, y = blank[i]
    for p in poss[i]:
        g[x][y] = p
        go(i+1, g, x, y)
        g[x][y] = 0
    
go(0, g, blank[0][0], blank[0][1])

처음에 빈칸마다 탐색해서 들어갈 수 있는 숫자 넣고 다시 탐색 반복 (시간초과)
한번만 탐색하고 재귀 돌리는 것으로 바꿈 (어떤 분의 풀이 참고..)

0개의 댓글