백준 알고리즘 2580번: 스도쿠 (Python)

문제 정보

---

2580번: 스도쿠

 

 

핵심

---

경우의 수가 엄청나게 많기 때문에, 파이썬의 경우 특히 시간초과에 대한 고민을 하면서 푸는것이 좋음

또한, 어떤식으로 풀어갈지 잡고 가는것이 가장 중요한 것 같다

 

 

풀이

---

문자열을 입력받아 2차원 정수형 배열을 만든다. 배열의 이름은 Pane

이를 뒤집은 배열(행-열) rPane을 만들어 준다 (열에 같은 수가 존재하는지 확인)

 

배열의 원소 중 0을 가진 좌표(빈 공간)을 blank 배열에 좌표 형태로 저장한다

해당 좌표에 올 수 있는 수를 계산하는데 계산하는 경우는 다음과 같다

 

1. 해당 좌표의 행, 열에 존재하지 않는 수를 possible 에 추가한다

2. 해당 좌표의 9개의 칸에 존재하는 수가 possible 에 존재한다면 remove를 통해 원소를 제거해 준다

+ 여기서 possible은 set() 자료형으로 추가, 삭제시 O(1)의 시간복잡도를 가진다

 

possible 의 원소들을 Pane의 해당 위치에 하나씩 넣어보면서 재귀호출을 실시한다

진행하다가 해당 좌표의 possible 이 더이상 존재하지 않다면 백트래킹을 통하여 이전 단계로 돌아가 남은 possible을 Pane에 추가시키면서 반복한다

 

반복 후 blank를 모두 탐색하였고, Pane이 완성되었다면 이를 출력해주고 프로그램을 종료시킨다

 

from sys import stdin

def check(row, col):
    possible = set()
    for p in range(1, 10):
        if p not in Pane[row] and p not in rPane[col]:
            possible.add(p)

    for r in range(row - (row%3), row - (row%3) + 3):
        for c in range(col - (col%3), col - (col%3) + 3):
            if Pane[r][c] in possible:
                possible.remove(Pane[r][c])

    return possible

def dfs(idx):
    # 종료 조건 : 빈칸이 없는 경우
    if idx == len(blank):
        for y in range(9):
            print(' '.join(str(Pane[y][x]) for x in range(9)))
        exit(0)
    r, c = blank[idx]
    pos = check(r, c)

    if not pos:
        return
    for p in pos:
        Pane[r][c] = p
        rPane[c][r] = p
        dfs(idx+1)
        Pane[r][c] = 0
        rPane[c][r] = 0


Pane = [list(map(int, stdin.readline().split(' '))) for _ in range(9)]
rPane = list(map(list, zip(*Pane)))
# 행 열을 뒤집은 2차원 배열 rPane

blank = []
for i in range(9):
    for j in range(9):
        if Pane[i][j] == 0:
            blank.append((i, j))
# blank에 빈 공간 좌표 추가(y, x)

dfs(0)

 

 

 

고찰

---

해당 풀이는 사실 통과한 풀이 중 비효율적인 풀이라고 생각한다

그렇기 때문에, 이를 보완한 다른 분의 풀이를 참고하여 공부하게 되었다

 

# https://www.acmicpc.net/source/49768146

def bt(n, k):
    global flag
    if n == k:
        flag = True
        return
    else:
        x, y = blank[k]
        for i in range(1, 10):
            if flag:
                return
            if not cnts_row[x][i] and not cnts_col[y][i] and not cnts_block[x // 3 * 3 + y // 3][i]:
                arr[x][y] = i
                cnts_row[x][i] = 1
                cnts_col[y][i] = 1
                cnts_block[x // 3 * 3 + y // 3][i] = 1
                bt(n, k + 1)
                cnts_row[x][i] = 0
                cnts_col[y][i] = 0
                cnts_block[x // 3 * 3 + y // 3][i] = 0


arr = [list(map(int, input().split())) for _ in range(9)]
cnts_row = [[0] * 10 for _ in range(9)]  # 각 행의 0~9숫자가 있는지 없는지 판단하는 2중리스트
cnts_col = [[0] * 10 for _ in range(9)]  # 각 열에 0~9숫자가 있는지 없는지 판단하는 리스트
cnts_block = [[0] * 10 for _ in range(9)]  # 각 사각형에 0~9숫자가 있는지 없는지 판단하는 리스트
blank = []  # 숫자가 비어있는 좌표

# i행에 0~9가 있는지 없는지 판단하는 리스트 만들기
for i in range(9):
    for j in range(9):
        if arr[i][j]:
            cnts_row[i][arr[i][j]] = 1
        else:
            blank.append([i, j])

# i열에 0~9가 있는지 없는지 판단하는 리스트 만들기
for i in range(9):
    for j in range(9):
        cnts_col[i][arr[j][i]] = 1

# i번째 사각형에 0~9가 있는지 없는지 판단하는 리스트 만들기
for i in range(9):
    for j in range(9):
        cnts_block[i // 3 * 3 + j // 3][arr[i][j]] = 1

flag = False
bt(len(blank), 0)
for i in range(9):
    print(*arr[i])

이분은 매번 possible을 검사하지 않고, 미리 각 행, 열, 사각형에 0-9까지의 숫자가 존재하는지 판단하는 리스트를 만들어서

이를 하나씩 추가, 삭제하는 과정을 반복하여 풀이하였다

시간적 효율성은 이 풀이가 훨씬 좋은것 같다

 

이 부분을 기억해서 비슷한 문제가 나오면 더 효율적인 방법으로 풀이할 수 있을 것 같다

 

 

참고

---

GitHub - dduneon/CodingTestPy