백준: 2580 스도쿠

문제

2580번: 스도쿠

 

문제 풀이

 가로, 세로와 3 X 3 영역을 확인하여 스도쿠 퍼즐에 채워지지 않은 숫자 중 알맞은 숫자를 채우는 문제이다. 채워지지 않는 곳은 0으로 제시된다. 따라서 0인 부분의 좌표를 찾고 해당 좌표에 어떤 값을 대입하면 되는지 확인하면 된다. 확인하는 방법은 다음과 같다.

 

• 한 행에 어떤 값이 없는지 확인한다.
• 한 열에 어떤 값이 없는지 확인한다.
  • 그래프의 행/열을 전환시켜 확인하면 쉽다.
• 3 X 3 영역에 어떤 값이 없는지 확인한다.

 

코드

from sys import stdin, exit

# 3 X 3 영역 확인
def area_check(area, num):
    x, y = map(lambda n: n // 3 * 3, area)
    for i in range(3):
        for j in range(3):
            if num == x_graph[x + i][y + j]:
                return False
    return True


def dfs(cur_find):
    if cur_find == len(zeros):
        for nums in x_graph:
            print(*nums)
        exit(0)

    for num in range(1, 10):
        next_x, next_y = zeros[cur_find]
        if row(next_x, num) and column(next_y, num) \
                and area_check([next_x, next_y], num):
            x_graph[next_x][next_y] = y_graph[next_y][next_x] = num
            dfs(cur_find + 1)
            x_graph[next_x][next_y] = y_graph[next_y][next_x] = 0


if __name__ == '__main__':
    x_graph = [list(map(int, stdin.readline().split())) for _ in range(9)]
    # 행/렬 전환
    y_graph = list(map(list, zip(*x_graph)))
    zeros = [(i, j) for i in range(9) for j in range(9) if not x_graph[i][j]]
    # 행에 값이 있는가?
    row = lambda x, num: num not in x_graph[x]
    # 열에 값이 있는가?
    column = lambda y, num: num not in y_graph[y]
    dfs(0)

 행/열을 확인하는 부분을 lamda로 작성하였고, lamda로 쉽게 처리하기 위해 기존의 그래프의 행/렬을 반전시켰다. 선택된 값을 체크하고 해제할 때, x_graph, y_graph 모두 진행해주어야 된다.