[ Baekjoon - 11/23 ] - 2239번: 스도쿠

문제 링크 : https://www.acmicpc.net/problem/2239

2239번: 스도쿠

 

소요 시간 : 2시간

스도쿠 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	13166	6440	4692	47.317%

문제

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

입력

9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

출력

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

제한

• 12095번 문제에 있는 소스로 풀 수 있는 입력만 주어진다.
  • C++17: 180ms
  • Java 15: 528ms
  • PyPy3: 2064ms

예제 입력 1 복사

103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

예제 출력 1 복사

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

 

---

 

1.  문제를 읽고 이해하기

▶ 입출력 형태 및 조건

맵 (9x9 맵 : [1, 9]) 

출력 > 9개의 줄에 9개의 숫자로 맵을 출력

 

 

▶ 문제

빈칸은 0, 아닌 칸은 1~9의 숫자로 9x9의 숫자가 주어졌을 때, 스도쿠의 룰에 맞게 정답을 출력하는 문제

 

 

▶ 시간, 메모리 제한 : 2초, 256MB

 

2.  문제를 익숙한 용어로 재정의와 추상화

스도쿠의 룰은 너무 잘 알고 있었어서 바로 3번을 진행했음

 

3.  문제 해결 방안

1st 접근 ) 해쉬맵으로 배열 1x9, 9x1, 3x3 각각을 생성해서 해당 칸에 넣지 못하는 아이들을 저장

1x9와 9x1박스는 일차원 배열로 저장하고, 3x3은 2차원 배열로 해당 칸에 이미 있는 아이들을 저장했다.

그리고 맵을 스캔하며,
1~9 라면, 해당 칸이 포함되어 있는 각 1x9, 9x1, 3x3 배열에 값을 저장하고,
0 이라면, 1x9, 9x1, 3x3 배열에 없는 값으로 다시 완탐을 돌렸다.

 

여기서 완탐을 BFS로 선택했었는데,  시간초과가 발생했다
지금 생각해보면 시간초과 안나오는게 이상했을 것 같긴 하다;

DFS로 바꾸어 도전해보니 시간초과가 나오긴했는데(Python 3), 파이파이로 제출해서 맞았습니다를 얻을 수 있었다. 

 

4.  위 계획 검증

스도쿠의 룰 대로 따라간거라 생략

 

5.  코드 작성

▶ PyPy3 ( 130628KB, 3300ms)

import sys
input = sys.stdin.readline

def dfs(n: int):
    if n == len(zeros):
        for i in sudoku:
            for j in i:
                print(j, end="")
            print()
        sys.exit()

    # 현재 가능한 아이들
    cur_candi = [i for i in range(1, 10)]

    # 1x9, 9x1, 3x3에서 값이 있으면 제거
    x, y = zeros[n]
    for i in range(9):
        if sudoku[x][i] in cur_candi:
            cur_candi.remove(sudoku[x][i])
        if sudoku[i][y] in cur_candi:
            cur_candi.remove(sudoku[i][y])

    x_, y_ = x // 3, y // 3
    for i in range(3 * x_, (x_ + 1) * 3):
        for j in range(3 * y_, (y_ + 1) * 3):
            if sudoku[i][j] in cur_candi:
                cur_candi.remove(sudoku[i][j])

    # 가능한 후보들로 한해 dfs로 찾아가기
    for i in cur_candi:
        sudoku[x][y] = i
        dfs(n + 1)
    sudoku[x][y] = 0

if __name__ == '__main__':
    sudoku = [list(map(int, list(input().rstrip()))) for _ in range(9)]
    zeros = [(i, j) for i in range(9) for j in range(9) if not sudoku[i][j]]
    dfs(0)

 

6.  결과

PyPy말고도 Python3으로 통과한 사람이 있어서 후에 다시 도전해보려 한다!