문제 링크
https://www.acmicpc.net/problem/2580
문제 유형
그래프 (DFS) + 백트래킹
🌈문제
스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.
나머지 빈 칸을 채우는 방식은 다음과 같다.
1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.
또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.
이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.
게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.
입력
아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.
0 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
0 6 0 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7
8 0 4 9 1 3 5 0 6
5 9 6 8 2 0 4 1 3
9 1 7 6 5 2 0 8 0
6 0 3 7 0 1 9 5 2
2 5 8 3 9 4 7 6 0출력
모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.
스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.
1 3 5 4 6 9 2 7 8
7 8 2 1 3 5 6 4 9
4 6 9 2 7 8 1 3 5
3 2 1 5 4 6 8 9 7
8 7 4 9 1 3 5 2 6
5 9 6 8 2 7 4 1 3
9 1 7 6 5 2 3 8 4
6 4 3 7 8 1 9 5 2
2 5 8 3 9 4 7 6 1💡 아이디어
이 문제를 처음 보았을 때, 아.. 백트래킹이다. 라고 감이 딱 왔다. 그러나 어떻게 어디서 접근해야 할지를 몰라서 한참을 종이에 끄적끄적 대면서 고민했었다.
백트래킹의 개념을 알고 있어도 이를 완전탐색에 활용하려고 하면 항상 막막하게 막히는 것 같아서 이번 기회에 잘 학습하고 싶어 글을 작성하게 되었다.
사실 스도쿠는 코드로 작성하는 것 말고도 비행기에서 여러번 해 봤을때 (ㅋㅋ) 나도 잘 못해서 이 문제를 처음 풀 때부터 조금 자신이 없었던 것 같다.
이 문제는 0이 있는 칸에 1~9 사이의 적절한 수를 넣어서 맞는지 확인을 하고 내가 넣어놓은 정보를 저장하고 다시 사용하고 활용해야 하기 때문에 백트래킹을 이용하는 것이다.
문제 해결 로직은 아래와 같다.
1. 빈칸인 부분의 위치를 알기 위하여 그 좌표를 blank라는 리스트에 담아 저장한다.
2. 빈칸에 1~9의 수를 담아본다. 그러나 이 때 넣을 수 있는 수인지 확인하는 과정을 거친다.
3. 다음 빈칸에 대하여 2번과 같은 과정을 반복하여 다른 수들에 대한 조사를 마친다.
4. 마지막 빈칸을 채우게 되면 맵을 출력하도록 한다.
👨💻 코드 작성
import sys
sudoku = []
blank = []
for _ in range(9):
sudoku.append(list(map(int, sys.stdin.readline().split())))
for i in range(9):
for j in range(9):
if sudoku[i][j] == 0:
blank.append((i,j))
def checkRow(x, a):
for i in range(9):
if a == sudoku[x][i]:
return False
return True
def checkCol(y, a):
for i in range(9):
if a == sudoku[i][y]:
return False
return True
def checkBox(x, y, a):
nx = x // 3 * 3
ny = y // 3 * 3
for i in range(3):
for j in range(3):
if a == sudoku[nx + i][ny + j]:
return False
return True
def dfs(idx):
if idx == len(blank):
for i in range(9):
print(*sudoku[i])
exit(0)
for i in range(1, 10):
x = blank[idx][0]
y = blank[idx][1]
if checkRow(x, i) and checkCol(y, i) and checkBox(x, y, i):
sudoku[x][y] = i
dfs(idx + 1)
sudoku[x][y] = 0
dfs(0)
blank라는 배열에 0이 들어가 있는 좌표를 저장한다. 그럼 dfs 함수에서는 무엇을 하나?
만약, dfs 함수가 모든 blank들을 탐색한다고 판단하면 ( idx == len(blank)) 결과를 출력하고 exit(0)을 이용하여 강제 종료한다.
그리고 아래 있는 for문인 for i in range(1, 10)은 1 ~ 9의 수를 탐색하는데, 빈칸을 하나씩 돌면서 해당 빈칸에 수가 들어갈 수 있는지 checkRow , checkCol, checkBox 함수를 이용하여 하나씩 체크하면서 스도쿠에 들어갈 수 있는지 확인하고, dfs 함수로 다음 blank를 검사한다. 만약, 해당 재귀함수를 돌다가 실패하는 경우가 발생하면 자연스럽게 리턴되고 sudoku[x][[y] = 0다시 0으로 만들어서 그 전의 일로 다시 돌아가서 하나하나씩 살펴본다.
처음 이 문제 채점을 맡겼을 때 python3로 하면 시간 초과가 나서 어디가 틀렸나 하고 input문을 sys 이용해서 바꿔 보기도 했는데, pypy3가 더 시간을 많이 줘서 이 친구로 채점하는 것이 나름의 꿀팁이다.
