[백준] 2580 스도쿠 - 골드 4

[오늘의 문제]

https://www.acmicpc.net/problem/2580

---

[오늘의 학습 키워드]

• 백트래킹

---

1. 문제설명

 

9 x 9 크기의 스도쿠가 주어지고 빈 칸은 0으로 입력된 보드게임판이 주어집니다.

 

스도쿠를 완성하는 코드를 작성하는 문제입니다.

---

[제한사항]

• 시간 제한 1초
• 메모리 제한 256MB
• PyPy3: 1172ms

---

2. 접근방식

 

스도쿠를 배열로 입력 받으니 해당 위치에 들어갈 수 있는 수를 가로, 세로, 박스로 검사한 뒤 모든 조건에 부합하는 수가 있다면 그 수를 넣고 스도쿠를 돌려보고, 모든 조건을 찾기 위해 백트래킹으로 구성하면 될 것 같습니다.

 

백트래킹 구성을 위해 sdoku 보드에 값을 넣었다가 다시 0으로 만드는 작업을 반복하며 빈 칸을 모두 채워 나가면 될 것 같습니다.

 

그러기 위해선 우선 전체 탐색을 통해 모든 빈칸의 위치를 저장하고 해당 빈 칸의 위치에 들어갈 수 있는 수를 찾는 조건을 찾아야 할겁니다.

 

1.9x9 배열을 전체 탐색하며 빈 칸의 위치 정보를 업데이트

 

2. 백트래킹 함수를 실행하여 모든 빈 칸을 채울 때까지 반복

 

3. 가로 검사, 세로 검사, 박스 검사 코드 작성

 

4. 모든 조건이 맞아 빈 칸을 다 채운 경우 스도쿠를 출력하고 종료

 

위 조건대로 코드를 구성하면 될 것 같습니다.

 

그러기 위해선 한가지 생각할 것이 필요한데 바로 박스 검사 부분 입니다.

 

예제 입력에서 스도쿠는 9 x 9 배열의 형태로 입력이 주어집니다.

 

그러나 박스검사는 3 x 3 크기의 형태로 0,0 / 0, 3 / 0, 6 / 3, 0 / 3, 3 / 3, 6 / 6, 0 / 6, 3 / 6, 6 위치마다 검사하며 해당 위치에서 3 x 3 검사를 실시해야 합니다.

 

그러면 기존의 스도쿠 배열에서 접근하기 상당히 까다로운데 조금만 생각해보면 됩니다.

 

우리가 검사를 시작하려는 위치는 빈 칸의 위치입니다.

 

예를 들어 빈 칸이 4, 7 위치에 있다고 생각해 보겠습니다.

 

4, 7 위치의 박스검사를 시행하려면 3, 6 위치에서 시작해주어야 합니다.

 

그럼 입력받은 4를 3으로 바꿔줘야 하고, 7을 6으로 바꿔줘야 합니다.

 

단순히 1씩 빼면 다른 위치에서 문제가 발생하니 3으로 나눠 수를 맞춰줘야 합니다.

 

입력받은 4를 3으로 나눈 몫은 1이 되겠죠 여기에 3을 곱해주면 3이 됩니다.

만약 3 이하의 수를 나눈 몫에 3을 곱하면 0이 됩니다.

그럼 6이상의 수를 3으로 나눈 몫에 다시 3을 곱하면 6이 되겠죠

 

이런식으로 0, 3, 6의 위치를 찾을 수 있는 겁니다.

여기에 3x3 탐색을 실시하며 계산된 위치에 + i를 실시하면 3 x 3 검사를 할 수 있습니다. 

 

이를 생각하며 코드를 구현해 보았습니다.

---

3. 코드

import sys
input = sys.stdin.readline

sdoku = [list(map(int, input().split())) for _ in range(9)]

def check_row(x, num):
    for j in range(9):
        if sdoku[x][j] == num:
            return False
    return True

def check_col(y, num):
    for i in range(9):
        if sdoku[i][y] == num:
            return False
    return True

def check_box(x, y, num):
    for i in range(3):
        for j in range(3):
            if sdoku[x//3 * 3 + i][y//3 * 3 + j] == num:
                return False
    return True

def find(n):
    # 종료 조건 -> 마지막 빈 칸 위치까지 다 채운 경우
    if n == len(blank):
        for s in sdoku:
            print(*s)
        exit()
    
    for num in range(1, 10):
        x = blank[n][0]
        y = blank[n][1]

        # 후보 찾기 -> 가로, 세로, 박스 검사해서 들어갈 수 있는 수만 넣기
        if check_row(x, num) and check_col(y, num) and check_box(x, y, num):
            sdoku[x][y] = num
            find(n + 1)
            sdoku[x][y] = 0

# 빈 칸 위치 찾아서 모두 업데이트
blank = []
for i in range(9):
    for j in range(9):
        if sdoku[i][j] == 0:
            blank.append((i, j))
find(0)

---

[코드 설명]

import sys
input = sys.stdin.readline

sdoku = [list(map(int, input().split())) for _ in range(9)]
.
.
.

# 빈 칸 위치 찾아서 모두 업데이트
blank = []
for i in range(9):
    for j in range(9):
        if sdoku[i][j] == 0:
            blank.append((i, j))
find(0)

 

sdoku로 입력을 받고 모든 빈 칸의 위치를 찾아 black 배열에 업데이트 해줍니다.

 

그 후 blank 배열의 0번 인덱스부터 마지막 인덱스까지 찾기 위한 find 함수를 정의하고 0번 인덱스부터 탐색을 시작합니다.

---

def find(n):
    # 종료 조건 -> 마지막 빈 칸 위치까지 다 채운 경우
    if n == len(blank):
        for s in sdoku:
            print(*s)
        exit()
    
    for num in range(1, 10):
        x = blank[n][0]
        y = blank[n][1]

        # 후보 찾기 -> 가로, 세로, 박스 검사해서 들어갈 수 있는 수만 넣기
        if check_row(x, num) and check_col(y, num) and check_box(x, y, num):
            sdoku[x][y] = num
            find(n + 1)
            sdoku[x][y] = 0

 

find 함수는 blank 배열의 0번 인덱스부터 저장된 0의 위치 정보를 하나씩 꺼내와 유효한 수를 찾아줄 것입니다.

 

그러기 위해 입력받은 0번 부터 blank의 마지막 인덱스까지 탐색을 실시하고 탐색이 종료되면 스도쿠가 완성되었을 테니 출력하고 강제종료 시켜줍니다.

 

return 대신 exit()를 사용한 이유는 스도쿠 배열에 들어갈 수 있는 수를 찾은 뒤 넣어보고 다음 find 함수를 실행하기 때문입니다.

 

그럼 반복문을 통해 1부터 9까지의 숫자 중에서 입력가능한 경우 넣어서 실행하고 안되면 종료되어 다시 0으로 바뀌니 for문이 넘어가며 다음 수를 넣어서 다시 find 함수를 실행합니다.

 

그럼 blank 배열의 n번 인덱스의 위치 정보에 들어갈 수 있는 모든 수를 넣어보고 다음 함수로 넘어갑니다.

 

그렇게 조건을 찾고 스도쿠를 완성하면 그냥 종료하면 됩니다.

왜냐하면 스도쿠는 정답이 1개만 존재하는게 아니기 때문입니다.

 

그 다음으로 해당 위치에 들어갈 수 있는 수의 후보를 찾기 위해 check_row, check_col, check_box 함수를 실행해 줄 겁니다.

 

이때, x 와 y 는 현재 빈칸의 위치정보 sdoku[x][y] 에 해당하고 x는 가로열, y는 세로 행에 해당합니다.

 

따라서 check 함수들을 실행할 때 필요한 정보와 현재 넣어보고자 하는 숫자가 맞는지 확인해 줄 겁니다.

---

def check_row(x, num):
    for j in range(9):
        if sdoku[x][j] == num:
            return False
    return True

def check_col(y, num):
    for i in range(9):
        if sdoku[i][y] == num:
            return False
    return True

def check_box(x, y, num):
    for i in range(3):
        for j in range(3):
            if sdoku[x//3 * 3 + i][y//3 * 3 + j] == num:
                return False
    return True

 

check_row 의 경우 입력받은 sdoku[x]번째 행의 y번째 위치에 들어갈 수를 찾는데 그 수를 num으로 받아왔습니다.

 

그럼 그 num 수와 sdoku[x][0 ~ 9] 까지 중 겹치는 수가 있으면 안되겠죠 따라서 9번 반복을 실시하며 x의 위치는 고정한 상태로 sdoku와 겹치는 수를 찾고 만약 겹치는 수가 있다면 그 수는 넣을 수 없으니 False를 반환하고

 

넣어도 되는 경우 True를 반환해 주었습니다.

 

동일한 방식으로 check_col을 구현하였고 check_box의 경우 앞서 3x3 탐색을 위해 찾은 방법을 토대로 해당 위치의 수와 동일한 수가 있는지 판별해 주었습니다.

 

이 수도 마찬가지로 동일한 수가 있다면 False를 반환하고 종료되고 없다면 True를 반환합니다.

 

이렇게 3가지 조건에 모두 맞는 경우 해당 수를 sdoku[x][y] 번째 위치에 넣고 다음 find를 실행하는 겁니다.

---

4. 결과

---

[회고]

이번 문제는 조건 자체는 간단하였는데 박스 탐색 조건이 헷갈렸습니다.

 

파이썬의 인덱스 탐색을 정말 잘 사용해야 하는 문제였는데 다른 문제들을 풀며 인덱스 탐색의 위치를 설정하는 방법들을 공부해봤어서 해결이 가능했습니다.

 

박스 탐색시 입력받은 수를 나눠 그 몫을 구하고 다시 3을 곱해 0, 3, 6의 위치를 찾은 순간 문제는 쉽게 해결이 가능하였습니다.

 

그 위치를 기준으로 탐색을 실시하여 조건을 찾을 수 있었습니다.

 

백트래킹은 대부분 조건이 많아 가지치기를 잘해주어야 하는데 이번 문제의 경우 별도의 가지치기 없이 수 탐색 조건만 잘 세우면 해결이 가능하였습니다. 특히 박스 탐색 조건이 까다롭지 그것만 아니라면 실버난이도의 문제 였던것 같습니다.

 

박스탐색 조건 방식을 응용한다면 백준의 상어시리즈에서 유용하게 이용 가능할 것입니다.

 

상어시리즈 문제들은 이미 해결하고 velog에 작성해 두었습니다. 궁금하시다면 여기서 관련 문제들을 확인하실 수 있습니다. https://velog.io/@swan/posts

swan (정수완) / 작성글 - velog