본 풀이는 유튜브 강의를 토대로 작성했습니다.
2239번: 스도쿠
스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다
www.acmicpc.net
문제 분석
- 스도쿠를 푸는 알고리즘을 작성해야 한다.
- 스도쿠의 각 칸에는 가로/세로/ 3 x 3 박스 내에 1~9까지 곂치는 수가 존재하지 않아야 한다.
본 문제를 풀이할 때 주의사항이 있다.
"가로/세로/ 3 x 3 박스 내에 1~9까지 곂치는 수"를 고려하여 문제를 풀었을 때 답이 나오지 않는 경우가 존재한다.
그럴 때는 이전 칸으로 돌아가서 조건에 맞는 다른 수로 수정해야 한다.
따라서 이 문제는 백 트래킹을 사용해야 한다.
알고리즘
1. 스도쿠에 빈 공간(0)이 있는지 확인한다.
2. 빈 공간이 없으면 스도쿠가 완성됐으므로 종료한다.
3. 빈 공간이 있으면 빈 공간(col, row)이 어딘지 말한다.
4. 빈 공간에 어떤 값(1~9)이 들어갈 수 있는지 탐색한다.
- 찾았다면 스도쿠에 채워넣는다.
- 채워넣을 수 있는 게 없다면 백 트래킹 한다.
스도쿠에 빈 공간 확인하기
1. 스도쿠 전체를 탐색하며 빈 공간(0)이 발견되면 해당 좌표를 리턴한다.
2. 스도쿠에서 빈 공간이 발견되지 않으면, None을 리턴한다.
빈 공간에 들어갈 수 있는 값인지 식별하기
빈 공간에 들어갈 수 있는 값인지 식별하기 위해서는 "가로 / 세로 / 3 x 3 박스"를 탐색해야 한다.
1. 가로 탐색
스도쿠의 column을 고정시키고 row 방향으로 이동 탐색을 진행한다.
들어가고자 하는 값이 발견되면 False를 리턴한다.
2. 세로 탐색
스도쿠의 row을 고정시키고 col 방향으로 이동 탐색을 진행한다.
들어가고자 하는 값이 발견되면 False를 리턴한다.
3. 3 x 3 박스 탐색
1. 탐색이 시작될 지점을 계산한다
2. 탐색시작 지점에서부터 3 x 3 지점을 탐색한다.
1. (7, 4) 지점이 속한 박스 영역의 시작 지점을 찾는다고 가정하자.
2. 왼쪽 그림의 경우 박스의 시작 지점은 (6, 3)이다.
3. 박스 영역의 시작 지점을 찾는 공식은 (컬럼좌표//3 * 3, 로우좌표//3 *3)이다.
("a//b"는 a와 b를 나눴을 때 몫과 나머지 중에 몫만 출력한다)
코드
import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")
def pretty_print():
for i in range(9):
for j in range(9):
print(board[i][j], end='')
print()
def find_empty():
for i in range(9):
for j in range(9):
if board[i][j] == 0:
return i, j
return None, None
def valid(col, row, val):
# 가로 축 점검
for i in range(9):
if board[col][i] == val:
return False
# 세로 축 점검
for i in range(9):
if board[i][row] == val:
return False
# 3x3 박스 점검
box_col = col // 3 * 3
box_row = row // 3 * 3
for i in range(3):
for j in range(3):
if board[box_col+i][box_row+j] == val:
return False
return True
def solution():
col, row = find_empty()
if col is None:
return True
else:
for i in range(1, 10):
if valid(col, row, i):
board[col][row] = i
if solution():
return True
board[col][row] = 0
return False
if __name__ == '__main__':
board = [list(map(int, input())) for _ in range(9)]
solution()
pretty_print()
'코딩 테스트' 카테고리의 다른 글
| [백준] 2839, 설탕 배달 | 최대한 상세히 설명하겠습니다 (0) | 2021.01.26 |
|---|---|
| [프로그래머스] 구명 보트, 파이썬| 최대한 상세히 설명하겠습니다 (0) | 2021.01.25 |
| [백준] 19942 다이어트 (0) | 2021.01.19 |
| [백준] 거스름돈 (0) | 2021.01.19 |
| [프로그래머스] 해킹 - 다익스트라 (0) | 2021.01.15 |
