[Python] 백준 2580 스도쿠

 

문제 분석

• 스토쿠 칸을 채우는 방법 :
  1. 각 가로, 세로 줄에는 1부터 9까지의 숫자가 한 번씩만 나타난다.
  2. 굵은 선으로 구분된 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타난다.

 

풀이

• 연산 횟수는 약 1초 → 연산은 약 1억 번
• 0인 값들을 찾고, 해당 값들에 대해 1~9까지 검사
• 1~9 중 없는 값에 대해 입력하는데
• 만약 입력할 수 있는 값이 여러 개이면, 다음 턴에 다시 검사
  
  
• 종료 조건
  
  • 스도쿠 안에 0이 없으면 종료

 

정답 코드

1차 - 시간 초과

import sys
input = sys.stdin.readline

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

def check(r, c, check_num) :
    # 가로, 세로
    for i in range(9):
        if check_num == sudoku[i][c]:
            return False
        if check_num == sudoku[r][i] :
            return False

    for i in range((r // 3)*3, (r // 3)*3 + 3) :
        for j in range((c // 3)*3, (c // 3)*3 + 3) :
            if check_num == sudoku[i][j] :
                return False
    return True

# 0의 위치가 담긴 리스트 생성
sum_total = 0
while True :
    # for i in range(9) :
    #     sum_total += sum(sudoku[i])
    # if sum_total == 405 :
    #     break

    li_0 = []
    for i in range(9):
        for j in range(9):
            if sudoku[i][j] == 0:
                li_0.append([i, j])

    if len(li_0) == 0 :
        break

    for r,c in li_0 :
        can_put_num = []
        for ck_num in range(1, 10) :
            if check(r, c, ck_num) :
                can_put_num.append(ck_num)
        if len(can_put_num) == 1:
            sudoku[r][c] = can_put_num[0]

# 정답 출력
for i in range(9) :
    print(' '.join(map(str, sudoku[i])))

 

2차 - 시간초과

import sys
input = sys.stdin.readline

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

def check(r, c, check_num) :
    # 가로, 세로
    for i in range(9):
        if check_num == sudoku[i][c]:
            return False
        if check_num == sudoku[r][i] :
            return False
    # 3x3
    for i in range((r // 3)*3, (r // 3)*3 + 3) :
        for j in range((c // 3)*3, (c // 3)*3 + 3) :
            if check_num == sudoku[i][j] :
                return False
    return True

li_0 = []
for i in range(9):
    for j in range(9):
        if sudoku[i][j] == 0:
            li_0.append([i, j])

while len(li_0) != 0 :
    for r,c in li_0 :
        can_put_num = []
        for ck_num in range(1, 10) :
            if check(r, c, ck_num) :
                can_put_num.append(ck_num)
        if len(can_put_num) == 1:
            sudoku[r][c] = can_put_num[0]
            del li_0[li_0.index([r,c])]

# 정답 출력
for i in range(9) :
    print(' '.join(map(str, sudoku[i])))

현재 방식은 백트래킹이 아닌 단순한 가능 숫자 리스트를 채우는 방식
여러번 리스트를 순회하며 가능한 숫자를 찾고 제거하는 방식으로 비효율적이다.

1. 불필요한 방식 줄이기
   • 따라서 현재 코드에서 li_0 리스트를 여러 번 순회하면서 가능한 숫자를 찾고, 그 중 유일한 값만을 채워 넣고 다시 반복하는 방식 사용
   • 하지만 한 번의 루프에서 li_0을 모두 탐색하고 단일 숫자가 확정된 경우를 찾는 방식은 불필요한 연산을 증가시킨다.
2. 백트래킹 도입
   • 스도쿠 문제는 일반적으로 백트래킹을 이용하여 해결하는 것이 가장 효율적이다.
   • 모든 경우를 탐색하는 것이 아니라 가능한 숫자를 하나씩 채워보면서 유망하지 않은 경우를 즉시 제거할 수 있다.

→ 백트래킹을 활용하여 DFS 재귀 방식 적용

 

3차 - 시간 초과

import sys
input = sys.stdin.readline

sudoku = [list(map(int, input().split())) for _ in range(9)]
blank = []
for i in range(9) :
    for j in range(9) :
        if sudoku[i][j] == 0 :
            blank.append((i,j))

def check(r, c, ch_num) :
    # 가로, 세로
    for i in range(9) :
        if sudoku[r][i] == ch_num or sudoku[i][c] == ch_num :
            return False
    # 3x3
    x = (r//3) * 3
    y = (c//3) * 3
    for i in range(x, x+3) :
        for j in range(y, y+3) :
            if sudoku[i][j] == ch_num :
                return False
    return True

# dfs & 백트래킹 : 한 칸씩 숫자를 채워가면서 유효한 경우만 탐색 - 불가능하면 되돌림
def solve(idx) :
    if idx == len(blank) : # 모든 빈 칸을 다 채우면 종료
        # 스도쿠 안의 0이 더 이상 없으면
        for i in range(9) :
            print(' '.join(map(str, sudoku[i])))
        sys.exit(0)

    r,c = blank[idx]
    for num in range(1,10) :
        if check(r, c, num) : # 가로, 세로, 3x3 통과
            sudoku[r][c] = num
            solve(idx+1)
            sudoku[r][c] = 0
solve(0)

check 부분을 쪼개볼까..

 

4차 - 시간 초과 : 쪼개는게 의미 없긴함..

import sys
input = sys.stdin.readline

sudoku = [list(map(int, input().split())) for _ in range(9)]
blank = []
for i in range(9) :
    for j in range(9) :
        if sudoku[i][j] == 0 :
            blank.append((i,j))

# def check(r, c, ch_num) :
#     # 가로, 세로
#     for i in range(9) :
#         if sudoku[r][i] == ch_num or sudoku[i][c] == ch_num :
#             return False
#     # 3x3
#     x = (r//3) * 3
#     y = (c//3) * 3
#     for i in range(x, x+3) :
#         for j in range(y, y+3) :
#             if sudoku[i][j] == ch_num :
#                 return False
#     return True

def ch_row(r, ch_num) :
    for i in range(9) :
        if sudoku[r][i] == ch_num :
            return False
    return True

def ch_col(c, ch_num) :
    for i in range(9) :
        if sudoku[i][c] == ch_num :
            return False
    return True

def ch_rect(r, c, ch_num) :
    x = (r//3) * 3
    y = (c//3) * 3
    for i in range(x, x+3) :
        for j in range(y, y+3) :
            if sudoku[i][j] == ch_num :
                return False
    return True

# dfs & 백트래킹 : 한 칸씩 숫자를 채워가면서 유효한 경우만 탐색 - 불가능하면 되돌림
def solve(idx) :
    if idx == len(blank) : # 모든 빈 칸을 다 채우면 종료
        # 스도쿠 안의 0이 더 이상 없으면
        for i in range(9) :
            print(' '.join(map(str, sudoku[i])))
        sys.exit(0)

    r,c = blank[idx]
    for num in range(1,10) :
        if ch_row(r, num) and ch_col(c, num) and ch_rect(r,c,num) : # 가로, 세로, 3x3 통과
            sudoku[r][c] = num
            solve(idx+1)
            sudoku[r][c] = 0
solve(0)

 

5차 - pypy 로 제출하니까 통과됨

import sys
input = sys.stdin.readline

sudoku = [list(map(int, input().split())) for _ in range(9)]
blank = []
for i in range(9) :
    for j in range(9) :
        if sudoku[i][j] == 0 :
            blank.append((i,j))

def check(r, c, ch_num) :
    # 가로, 세로
    for i in range(9) :
        if sudoku[r][i] == ch_num or sudoku[i][c] == ch_num :
            return False
    # 3x3
    x = (r//3) * 3
    y = (c//3) * 3
    for i in range(x, x+3) :
        for j in range(y, y+3) :
            if sudoku[i][j] == ch_num :
                return False
    return True

# def ch_row(r, ch_num) :
#     for i in range(9) :
#         if sudoku[r][i] == ch_num :
#             return False
#     return True
#
# def ch_col(c, ch_num) :
#     for i in range(9) :
#         if sudoku[i][c] == ch_num :
#             return False
#     return True
#
# def ch_rect(r, c, ch_num) :
#     x = (r//3) * 3
#     y = (c//3) * 3
#     for i in range(x, x+3) :
#         for j in range(y, y+3) :
#             if sudoku[i][j] == ch_num :
#                 return False
#     return True

# dfs & 백트래킹 : 한 칸씩 숫자를 채워가면서 유효한 경우만 탐색 - 불가능하면 되돌림
def dfs(n) :
    if n == len(blank) : # 모든 빈 칸을 다 채우면 종료
        # 스도쿠 안의 0이 더 이상 없으면
        for i in range(9) :
            print(' '.join(map(str, sudoku[i])))
        sys.exit(0)

    r,c = blank[n]
    for num in range(1,10) :
        if check(r, c, num) : # 가로, 세로, 3x3 통과
            sudoku[r][c] = num
            dfs(n+1)
            sudoku[r][c] = 0
dfs(0)

 

 

2회차 - 25.02.19

1차 - 시간초과

import sys
input = sys.stdin.readline

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

# 0인 값들 찾기
lo_zero = []
for i in range(9) :
    for j in range(9) :
        if sudoku[i][j] == 0 :
            lo_zero.append([i,j])

def check(r, c, ch_num) : # 현재 0의 위치 & 체크할 숫자
    for i in range(9) :
        # 가로
        if sudoku[r][i] == ch_num :
            return False
        # 세로
        if sudoku[i][c] == ch_num :
            return False
        # 3x3
        nr = (r//3) * 3
        nc = (c//3) * 3
        for i in range(nr, nr+3) :
            for j in range(nc, nc+3) :
                if sudoku[i][j] == ch_num :
                    return False
    return True

def dfs(n) :
    if n == len(lo_zero) : # 도든 0의 자리를 다 체크
        for i in range(9) : # 출력 및 종료
            print(' '.join(map(str, sudoku[i])))
        exit(0)

    r, c = lo_zero[n] # 아직 다 체크하지 않았다면 현재
    for num in range(1, 10) :
        if check(r, c, num) :
            sudoku[r][c] = num # 숫자를 채우고
            dfs(n+1) # 다음 칸으로 이동
            sudoku[r][c] = 0 # 선택한 숫자가 답이 아니라면 되돌리기 (0으로 원상복구) - 백트래킹

dfs(0) # lo_zero[0] 부터 검사

 

2차

시간 초과 수정 1

0의 위치를 저장(리스트 초기화)할 때
리스트를 사용하여 초기화 했더니 시간 초과

튜플 vs 리스트
튜플 ((i, j)): 불변(immutable) → 수정할 필요 없는 데이터 저장에 적합
리스트 ([i, j]): 가변(mutable) → 이후 값을 변경할 가능성이 있는 경우 유리

따라서 값 변경이 없으므로 튜플을 사용하는 것이 메모리적으로 더 효율적이다.

 

시간 초과 수정 2

sys.exit(0) vs exit(0)

• 코드 1: sys.exit(0)
• 코드 2: exit(0)
• sys.exit(0)과 exit(0)의 차이:
  • sys.exit(0): sys 모듈의 함수를 사용하여 프로그램을 종료 → 일반적으로 더 권장됨
  • exit(0): 내장 함수지만, sys.exit()와 다르게 인터프리터 환경에서는 SystemExit 예외를 발생시키지 않음
    → 스크립트가 아닌 인터프리터 환경에서는 exit(0)이 동작하지 않을 수 있음
  → 코드 1 (sys.exit(0))이 더 안전한 방식

 

시간 초과 수정 3

세로 & 가로 한 번에 체크

 

애초에 3x3 계산하는 부분이 잘못되었음..

 

import sys
input = sys.stdin.readline

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

blank = []
for i in range(9):
    for j in range(9):
        if sudoku[i][j] == 0:
            blank.append((i, j))

def check(r, c, ch_num): # 현재 0의 위치 & 체크할 숫자
    for i in range(9):
        if sudoku[r][i] == ch_num or sudoku[i][c] == ch_num:
            return False
    # 3x3
    x = (r // 3) * 3
    y = (c // 3) * 3
    for i in range(x, x + 3):
        for j in range(y, y + 3):
            if sudoku[i][j] == ch_num:
                return False
    return True

def dfs(n):
    if n == len(blank):  # 도든 0의 자리를 다 체크
        for i in range(9):  # 출력 및 종료
            print(' '.join(map(str, sudoku[i])))
        sys.exit(0)

    r, c = blank[n]  # 아직 다 체크하지 않았다면 현재
    for num in range(1, 10):
        if check(r, c, num):
            sudoku[r][c] = num  # 숫자를 채우고
            dfs(n + 1)  # 다음 칸으로 이동
            sudoku[r][c] = 0  # 선택한 숫자가 답이 아니라면 되돌리기 (0으로 원상복구) - 백트래킹

dfs(0)  # lo_zero[0] 부터 검사

 

 

백트래킹 핵심

각 단계에서 가능한 숫자를 하나 넣고, 다음 빈칸을 재귀적으로 탐색하면서 답을 찾는 방식이다.
만약 현재 선택한 숫자가 정답이 아니라면, 되돌리기(백트래킹) 해서 다른 숫자 시도

---

🔥 동작 원리 (백트래킹)

for num in range(1, 10):  # 1부터 9까지 넣을 수 있는 숫자 후보 탐색
    if check(r, c, num):  # 현재 숫자가 유효한지 확인
        chess[r][c] = n  # 숫자 채우기
        dfs(n + 1)  # 다음 빈칸으로 이동 (재귀 호출)
        chess[r][c] = 0  # 되돌리기 (백트래킹)

🔍 동작 흐름 (예제)

빈칸이 아래와 같은 위치에 있다고 가정하자.

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

🚀 백트래킹 탐색 과정

1. 첫 번째 빈칸 (0,2)에 1을 넣고 진행
2. 다음 빈칸 (0,3)에 1을 넣었더니 규칙을 위반하면 되돌아감 (chess[0][3] = 0)
3. (0,3)에 2를 넣고 진행, 다시 다음 칸으로 이동
4. 만약 나중에 틀린 숫자가 발견되면 되돌아가서 다른 숫자를 시도
5. 마지막 빈칸까지 채워지면 종료

---

💡 백트래킹을 왜 하는 걸까?

• 스도쿠는 정답이 하나일 수도 있지만, 없을 수도 있고, 여러 개일 수도 있다.
• 모든 가능한 경우를 탐색하면서 정답을 찾아야 하기 때문에 백트래킹 필요
• 현재 숫자가 맞다고 가정하고 진행했다가, 나중에 문제가 생기면 되돌아가서 다시 다른 숫자로 시도하는 방식

---

🔥 백트래킹 동작을 코드로 표현하면?

아래 그림처럼 재귀적으로 진행하다가, 틀린 경우 되돌아가면서 다시 다른 숫자로 채우는 방식이야.

1을 넣음 → 다음 칸 이동 → 2를 넣음 → 다음 칸 이동 → 만약 안 맞으면 되돌아감
  ↓               ↓               ↓
(0,2)=1  →  (0,3)=2  →  (0,4)=3   →  만약 틀림? 되돌아가기
                 ↑               ↑
          (0,3) 되돌리고 3 넣어보기  →  (0,4)도 되돌리고 4 넣어보기

---

✅ 핵심 정리

1. 빈칸을 채울 수 있는 숫자를 하나씩 넣고 (chess[r][c] = n)
2. 다음 빈칸을 dfs()로 재귀 호출해서 탐색
3. 만약 나중에 규칙을 위반하면 chess[r][c] = 0 으로 되돌려서 다른 숫자로 시도
4. 모든 빈칸을 채우면 정답이므로 출력하고 종료 (exit(0))
5. 결국 "가능한 모든 경우를 탐색하되, 중간에 잘못된 경우는 빨리 되돌리는" 백트래킹 방식! 🚀🔥