백준 2580 스도쿠 문제
https://www.acmicpc.net/problem/2580
파이썬 코드
import sys
board = []
zero = []
row_sum = [0 for _ in range(9)]
column_sum = [0 for _ in range(9)]
rec_sum = [0 for _ in range(9)]
for i in range(9):
board.append(list(map(int, input().split())))
for i in range(9):
for v in range(9):
if board[i][v] == 0 :
zero.append([i, v])
def check(index, r, c):
number_set = {1, 2, 3, 4, 5, 6, 7, 8, 9}
for i in range(9):
if board[r][i] in number_set:
number_set.remove(board[r][i])
if board[i][c] in number_set:
number_set.remove(board[i][c])
for i in range(r - r%3 , r - r%3 +3):
for v in range(c- c%3 , c- c%3 +3):
if board[i][v] in number_set:
number_set.remove(board[i][v])
return number_set
def dfs(index, number):
global reset
if index != 0:
prev_r, prev_c = zero[index - 1]
board[prev_r][prev_c] = number
if index == len(zero):
for n in range(9):
print(" ".join(map(str, board[n])))
sys.exit()
r, c = zero[index]
for number in check(index, r, c):
board[r][c] = number
dfs(index+1, number)
board[r][c] = 0
dfs(0, 0)문제 풀이 방법
스도쿠 문제는 구현하는 것은 어렵지 않다고 생각한다. 조건에 맞추어서 작성하면 되는데 시간초과가 나는게 문제라고 생각한다.
이 문제 풀이는 dfs를 이용한 풀이로 다양한 경우의 수를 탐색하면서 스도쿠가 다 채워진다면 그 스도쿠를 출력하고 동작을 멈추는 프로그램이다.
의문점
처음에는 stack을 이용해서 dfs를 작성했다. 그런데 계속 시간 초과가 나서 어떤게 문제이지 하고 관련 자료를 찾던 도중 stack을 이용한 while문 대신에 재귀함수를 이용하면 시간이 더욱 줄어든다는 것이였다.
dfs 구현 방법을 위의 코드와 같이 재귀함수로 구현하자 시간내로 통과할 수 있었다.
그렇다면 stack과 재귀함수가 동작하는 것이 어떻게 다른가??
반복문 VS 재귀함수
역방향 vs 정방향
반목문에서는 stack 에 쌓아지는 숫자들이 역방향이다. 예를 들어서 특정 노드가 갈 수 있는 숫자가 1,2,3,4 라면 stack에 순서대로 1,2,3,4가 쌓이게 되고 4 숫자 먼저 밖으로 나가서 다시 반복문을 돌게 되어 있다.
하지만 재귀함수는 특정 노드가 갈 수 있는 숫자가 1,2,3,4 라면 다음 재귀는 1이라는 숫자부터 돌게 되어 있다
하지만 이 차이가 스도쿠 문제풀이에 큰 영향을 줄까??
물론 특정 문제에 따라서 어떠한 숫자를 먼저 탐색하는 가에 따라서 문제 풀이 시간은 달라 질 수 있지만 문제마다 다르기 때문에 큰 영향을 주지 않을 것이라 생각한다.
스도쿠 조건이 안맞을때 (백트래킹)
만약 dfs를 돌다가 스도쿠의 조건이 안맞아서 해당 노드에 대한 것을 삭제하고 다시 뒤로 돌아가야할 상황이 생길 것이다.
이때 반복문으로 dfs를 구현하게 된다면 해당 부모노드로 돌아가면서 스도쿠 판의 정보를 되돌려야한다. 혹은 각 경우마다 스도쿠판을 복사해서 넘겨준다면 해결될 것이다.
재귀함수로 dfs를 구현한다면 자식노드들이 차례대로 재귀함수가 끝나면서 스도쿠판을 스스로 복귀시키면서 함수를 종료하게 된다.
이러한 차이점은 스도쿠 문제풀이를 하는데 있어서 시간적인 차이를 발생한다!!!
느낀점
물론 코드를 보았을 때 더 확인하고 이해하기 쉬운 것은 반복문을 활용한 dfs 일 것이다.
하지만 백트래킹을 바탕으로 알고리즘 풀이를 한다면(시간 초과 가능성을 생각해야한다면!)
재귀함수를 통해서 dfs와 백트래킹을 구현해야 더 효율적인 코드를 작성할 수 있을 것이다.
