[백준/G4] 스도쿠

오랜만에 알고리즘 포스팅

 

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

 

 

 

 

 

특이점

 

전형적인 백트래킹 문제...라고 생각했다.

같은 로직을 java로 풀었을 때에는

 

408ms가 나왔다.

 

심지어 python3으로는 풀리지 않는다...

 

 

코드

import sys,math
from collections import deque
input= sys.stdin.readline

li = []

for _ in range(9):
    li.append(list(map(int,input().split())))


def check(row,col,num):
    # 행 검사
    for i in range(9):
        if li[row][i]==num:
            return False
            
    for i in range(9):
        if li[i][col]==num:
            return False
        
    block_row= (row//3)*3
    block_col= (col//3)*3

    for r in range(block_row, block_row + 3):
        for c in range(block_col, block_col + 3):
            if li[r][c] == num:
                return False
    return True

def dfs(row,col):
    if row==9:
        for i in range(9):
            print(*li[i])
        sys.exit(0)
        return
    
    if col==9:
        dfs(row+1,0)
        return

    if li[row][col]!=0:
        dfs(row,col+1)
        return

    for num in range(1,10):
        if check(row,col,num):
            li[row][col]=num
            dfs(row,col+1)
            li[row][col]=0

dfs(0,0)

 

해설

 

재귀함수에 row,col를 넘겨준 뒤, li의 원소가 0인 지점에서,

가능한 숫자의 조합을 check를 통해 판단하고 적용한뒤 백트래킹을 통해 복구해준다.

 

row가 9가 되었다는 것은 0~8 행의 적용이 끝났다는 것이므로 바로 출력하고 종료한다.

 

 

백트래킹+ 재귀 방식이다보니,  함수 호출이 잦아 그만큼 느려지는 건가 싶기도 하고??

check같은 함수를 최적화 하려면 할 수 있겠다는 생각은 든다.

 

문제를 푸는 것도 어려웠는데 막상 언어의 차이로 새로 찾아봐야 할 내용이 계속 생기니 좀 어지럽다

---

마치며

요 며칠 정글에서의 과제가 너무 많아서 하루의 공부 분량을 제대로 못 끝내는 경우가 생기곤 했다.

원래 월요일이면 과제는 다 보고 내가 모르는 부분을 찾아 정리하는 시간이 되어야 하는데... 점점 어려워지고 있다.

 

코치님들이 정글에서 할 수 있는 일에 집중하라고 말씀하신 것도 좀 더 와닿는다.

다만 난 아직 100%를 끌어내지 못했다고 생각한다. 

 

아직 "정글에서 주는 것도 하고 내 공부도 하면 되지?" 하는 욕심을 못 버렸다.

 

덜 맞아서 그런가보다.