🐷전동준(Jeon DongJun)

Go with the flow

[BOJ/백준-Python]2580번 - 스도쿠

2580번 - 스도쿠

문제

스도쿠는 18세기 스위스 수학자가 만든 ‘라틴 사각형’이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

나머지 빈 칸을 채우는 방식은 다음과 같다.

각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

입력

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

출력

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

제한

12095번 문제에 있는 소스로 풀 수 있는 입력만 주어진다.
- C++14: 80ms
- Java: 292ms
- PyPy3: 1172ms

예제 입력 1

3 5 4 6 9 2 7 8
8 2 1 0 5 6 0 9
6 0 2 7 8 1 3 5
2 1 0 4 6 8 9 7
0 4 9 1 3 5 0 6
9 6 8 2 0 4 1 3
1 7 6 5 2 0 8 0
0 3 7 0 1 9 5 2
5 8 3 9 4 7 6 0

예제 출력 1

3 5 4 6 9 2 7 8
8 2 1 3 5 6 4 9
6 9 2 7 8 1 3 5
2 1 5 4 6 8 9 7
7 4 9 1 3 5 2 6
9 6 8 2 7 4 1 3
1 7 6 5 2 3 8 4
4 3 7 8 1 9 5 2
5 8 3 9 4 7 6 1

해결할 방법을 생각해보자.💡

스도쿠를 푸는 문제다.

스도쿠를 할 때를 생각해보면 내가 푸는 방법이 있었다.

가로 방향으로 한 줄일 때 1~9가 중복되서 들어갈 수 없다.

세로 방향도 동일하다.

그리고 해당 칸이 위치하고 있는 9x9짜리 크기의 사각형 내에도 동일하다.

물론 대각선으로 보았을 때도 동일하다.

이렇게 네 가지 조건이 있는데 대각선 조건을 제외하고 세 가지 조건만 생각해서 하루종일 코드를 짜보았다.

import sys

sudoku = []

for i in range(9):
    row = list(map(int, sys.stdin.readline()[:-1].split()))
    sudoku.append(row)

list1 = [0,1,2]
list2 = [3,4,5]
list3 = [6,7,8]
nums = [x for x in range(1, 10)]

def check_row(row):
    N_exist1 = []
    for _ in range(1, 10):
        if _ not in row:
            N_exist1.append(_)

    return N_exist1

def check_col(table, x):
    N_exist2 = []
    for _ in range(9):
        if table[_][x] == 0:
            continue
        else:
            N_exist2.append(table[_][x])
    return N_exist2

def check_square(x, y, z):
    N_exist3 = []
    global list1, list2, list3, nums
    if x in list1:
        a = list1
    elif x in list2:
        a = list2
    else:
        a = list3

    if y in list1:
        b = list1
    elif y in list2:
        b = list2
    else:
        b = list3


    for _i in a:
        for _j in b:
            if z[_i][_j] == 0:
                continue
            else:
                N_exist3.append(z[_i][_j])

    return N_exist3




for i in range(9):
    for j in range(9):
        if sudoku[i][j] not in nums:
            m1 = check_row(sudoku[i])
            m2 = check_col(sudoku, j)
            m3 = check_square(i,j,sudoku)
            fill = list(set(m1)-set(m2)-set(m3))[0]
            sudoku[i][j] = fill
        
    print(' '.join(map(str, sudoku[i])))

백준 문제를 풀 때 vsc환경에서 풀고 있는데 여기서는 출력이 잘 되지만 백준에 제출하면 어째서인지 계속 런타임에러(인덱스) 가 발생한다. 인덱스를 사용하는 부분을 찾아봐도 아무리 모르겠다 ㅠㅠ

그래서 결국 또 다른 사람들이 한 것을 찾아보았따 ..하하 (안 좋은 습관..)

참고 블로그 : https://coder38611.tistory.com/137

다음에 더 공부해서 다시 풀어봐야겠다.

코드 💻

import sys

sudoku = [list(map(int, sys.stdin.readline().split())) for x in range(9)]

zeros = [(i,j) for i in range(9) for j in range(9) if sudoku[i][j] == 0]

def check(row, col):
    tmp = set(range(1, 10)) - set(sudoku[row])
    test = set()
    for i in range(9):
        test.add(sudoku[i][col])
    tmp -= test
    test = set()
    for i in range(row//3*3, row//3*3+3):
        for j in range(col//3*3, col//3*3+3):
            test.add(sudoku[i][j])
    tmp -= test
    return tuple(tmp)

def dfs(i):
    if i == len(zeros):
        [print(*row) for row in sudoku]
        sys.exit()
    row, col = zeros[i]
    tmp = check(row, col)
    for num in tmp:
        sudoku[row][col] = num
        dfs(i+1)
        sudoku[row][col] = 0

dfs(0)

해결 로그

문제 푼 날짜	체크
2022-08-17	✔

2022 196
2021 22

맨 위로 이동 ↑