[백준 - Python] 2580 - 스도쿠

0.  문제 링크

 

 

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

2580번: 스도쿠

---

1.  풀이 방법

 

 

의외로 방법은 심플하다.

그냥 row, col, 3 * 3 구역 내에서 넣을 수  있는 숫자를 찾으면 된다.

그리고 그 방식으로 DFS를 했다.

근데 문제는 이런 방식으로 했을 때, 스도쿠가 전부 채워지지 않으면 다시 넣을 수 있는 숫자를 찾아야 하는 것...

분명 다른 방법이 있을텐데, 나는 해당 방법 말고는 딱히 떠오르지 않았다.

 

아무튼 이렇게 하니까 시간 초과가 나서 pypy3로만 풀었다..ㅠㅠ

---

2.  코드

 

 

import sys
from collections import deque


def sol():
    while coordinate:
        y, x = coordinate.popleft()
        # candidate = candidate_dict.get((y, x), check_row(*check_col(*check_area(y, x))))
        if (y, x) not in candidate_dict:
            candidate = check_area(y, x)
            candidate = check_col(candidate, y, x)
            candidate = check_row(candidate, y, x)
            candidate_dict[(y, x)] = candidate
        candidate = candidate_dict[(y, x)]
        for i in candidate:
            if i > maps[y][x]:
                maps[y][x] = i
                before.append((y, x))
                break
        else:
            coordinate.appendleft((y, x))
            maps[y][x] = 0
            candidate_dict.pop((y, x))
            coordinate.appendleft(before.pop())
    for m in maps:
        print(*m, sep=' ')


def check_area(y, x):
    c_y = (y // 3) * 3
    c_x = (x // 3) * 3
    candidate = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    for i in range(c_y, c_y + 3):
        for j in range(c_x, c_x + 3):
            if maps[i][j] in candidate:
                candidate.remove(maps[i][j])
    # print(candidate)
    return candidate


def check_col(candidate, y, x):
    for m in maps:
        if m[x] in candidate:
            candidate.remove(m[x])
    return candidate


def check_row(candidate, y, x):
    for m in maps[y]:
        if m in candidate:
            candidate.remove(m)
    return candidate


if __name__ == "__main__":
    maps = [list(map(int, sys.stdin.readline().split())) for _ in range(9)]
    coordinate = deque()        # 들어가야 하는 좌표들
    before = deque()        # 이미 값이 할당되었던 좌표들
    for i in range(9):
        for j in range(9):
            if maps[i][j] == 0:
                coordinate.append((i, j))
    candidate_dict = dict()
    sol()

---

3.  마무리