[Python] 백준 - 2580 스도쿠

백준 - 2580 스도쿠

 

필요한 도구

 

 

1. 가로, 세로, 3x3 각 방문리스트

2. '0'이 있는 위치를 저장한 리스트 = zero

3. dfs 백트래킹 알고리즘

 

문제해결방법

 

 

1. 방문리스트를 가로, 세로, 3x3 공간에 없는 숫자를 체크할 수 있도록 이미 있는 숫자를 반영해둔다.

2. 위 3가지 리스트에 없는 숫자들을 빈자리에 채워넣으며, dfs가 호출된 횟수가 len(zero)와 같아지면 모두 채워졌다는 뜻이니, 출력한다.

 

- 코드

game = [list(map(int, input().split())) for _ in range(9)]
v_sero = [[0 for _ in range(10)] for _ in range(9)]
v_garo = [[0 for _ in range(10)] for _ in range(9)]
v_3x3 = [[0 for _ in range(10)] for _ in range(9)]
zero = []

for i in range(9):
    for j in range(9):
        if game[i][j] == 0:
            zero.append((i, j))
        else:
            v_sero[j][game[i][j]] = 1
            v_garo[i][game[i][j]] = 1
            v_3x3[i//3*3+j//3][game[i][j]] = 1
			

def dfs(idx):
    if idx == len(zero):
        for i in range(9):
            print(*game[i])
        sys.exit()
        return
    x, y = zero[idx]
    z = x//3*3+y//3
    for i in range(1, 10):
        if v_sero[y][i] == 0 and v_garo[x][i] == 0 and v_3x3[z][i] == 0:
            v_sero[y][i] = 1
            v_garo[x][i] = 1
            v_3x3[z][i] = 1
            game[x][y] = i
            dfs(idx+1)
            game[x][y] = 0
            v_sero[y][i] = 0
            v_garo[x][i] = 0
            v_3x3[z][i] = 0          

dfs(0)