[Python] 백준 2580 스도쿠

1. 문제 링크

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

2580번: 스도쿠

 

2. 문제 요약

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

3. 아이디어 정리

• 백트래킹으로 진행

1. 0으로 된 부분 모두 수를 채운 경우 그만
2. 0으로 된 좌표에 어떤 값이 가능한지 모두 백트래킹 진행

 

4. 문제 풀이

4-1. 내 풀이

import sys

def pos(x, y):
    """
    해당 좌표가 가능한 수 얻기
    """
    p = set(range(1, 10))
    # 1. 가로줄, 세로줄에 있는 수 제거
    for i in range(9):
        if graph[x][i] in p:
            p.remove(graph[x][i])
        if graph[i][y] in p:
            p.remove(graph[i][y])
    # 2. 굵은 선으로 구분되어 있는 3x3 수 제거
    x = x // 3   # 몇 번째 큰 칸에 있는지
    y = y // 3
    for i in range(x * 3, (x + 1) * 3):
        for j in range(y * 3, (y + 1) * 3):
            if graph[i][j] in p:
                p.remove(graph[i][j])
    return p

def dfs(cnt):
    if cnt == len(zero):     # 1. Base condition(종료 조건)
        [print(*a) for a in graph]
        sys.exit()
    x, y = zero[cnt]         # 0인 좌표 얻기
    for i in pos(x, y):      # 2. 해당 좌표가 들어갈 수 있는 값 얻어 백트래킹
        graph[x][y] = i
        dfs(cnt + 1)
        graph[x][y] = 0

graph = [list(map(int, sys.stdin.readline().split())) for _ in range(9)]
zero = [(i, j) for i in range(9) for j in range(9) if graph[i][j] == 0]

dfs(0)

 

 

5. 결론

• 백트래킹 문제