[DFS/BFS/완전탐색] 2580번 - 스도쿠(DFS, 백트래킹)

[백준] 2580번 - 스도쿠

풀이 시간: 70분 이내

(한줄평) 어렵진 않았으나 오류를 고치는데 시간이 걸린 문제. 한번쯤 복습 필요!!

스도쿠는 어렸을 때부터 많이 해봤기 때문에 딱히 아이디어를 떠올릴 필요가 없이 쉽게 구현할 수 있었다. 다만 나의 고정관념으로 인해 생긴 문제들때문에 오류를 고치느라 시간이 좀 걸렸다. 

(풀이1) DFS를 이용한 시간초과, 틀렸습니다 실패 코드

1) 문제 해결 아이디어

첫번째 오류. 시간 초과

1. Python3으로 제출하였더니 5%까지 되다가 시간초과가 떴다.

2. PyPy3로 제출했더니 11%까지 되다가 시간초과가 떴다.

3. target을 리스트 대신 집합으로 선언하고 discard()를 썼지만 여전히 11%까지 되다가 시간초과가 떴다.

4. graph를 temp라는 곳에 복사하는데 deepcopy를 썼는데 이게 시간이 굉장이 오래걸린다고 한다. 그래서 deepcopy를 쓰지 않고 dfs 후에 입력했던 값을 0으로 원상복귀 시켜주는 식으로 바꿨는데 30%까지 되다가 틀렸습니다가 떴다.

예전에 풀었던 문제에서 2차원 리스트를 다루다 보니 deepcopy를 써야만 했던 문제가 있었는데 이 문제도 당연하게 2차원 리스트니까 deepcopy를 써서 해결해야겠다는 고정관념이 불러온 참사였다. 2차원 리스트를 다루는 문제라고 해서 모두 deepcopy를 써야하는 것은 아니다!! 이 문제는 dfs를 한 번 호출하면 무조건 현재 빈칸에 해당하는 값 1개만 바뀌기 때문에 굳이 deepcopy를 쓸 필요가 없고 dfs 후에 원래 값으로 원상복귀만 해주면 된다!!

 

두번째 오류. 틀렸습니다

1. 일단 여러가지 답이 나올 수 있다는 점에서 처음 찾은 답 한 가지만 출력하고 더이상 다른 답을 출력하면 안된다! 이를 처리하는 코드가 없어서 틀렸다...

정답 찾음 여부를 체크하는 플래그 변수(find)를 전역변수로 False로 생성하고 dfs 시작 부분에 답을 아직 찾지 못했을 경우(False)일 때만 아래 코드를 진행시킨다. 처음 답을 찾았을 때 정답을 출력하고 종료하기 전에 find값을 True로 바꿔준다. 

 

2) 소스코드

import sys
from copy import deepcopy

# DFS
def dfs(depth, graph):
  # 빈 칸을 다 채우면
  if depth == blank_num:
    for i in graph:
      print(*i)
    return
  temp = deepcopy(graph)  # 깊은 복사
  # 빈 칸을 다 채우지 못했으면
  x, y = blank[depth]  # depth번째 빈칸 좌표
  target = [1, 2, 3, 4, 5, 6, 7, 8, 9]  # 넣을 수 있는 숫자 목록
  # 1. 가로줄, 세로줄에 있는 숫자 없애기
  for i in range(9):
    if temp[x][i] in target:  target.remove(temp[x][i])  # 가로줄
    if temp[i][y] in target:  target.remove(temp[i][y])  # 세로줄 
  # 2. 정사각형 칸에 있는 수 없애기
  for i in range(3):
    for j in range(3):
      if temp[(x // 3) * 3 + i][(y // 3) * 3 + j] in target:
        target.remove(temp[(x // 3) * 3 + i][(y // 3) * 3 + j])   
  # 가능한 숫자 중에 선택하기
  for i in target:
    temp[x][y] = i  # 숫자 쓰기
    dfs(depth + 1, temp)
    temp[x][y] = 0  # 원상복귀

# 9 * 9 스도쿠(0: 빈칸)
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(9)] 
blank = []
blank_num = 0  # 빈칸 개수
# 상, 하, 좌, 우
dx = [-1 ,1, 0, 0]
dy = [0, 0, -1, 1]

# 빈 칸 찾기
for i in range(9):
  for j in range(9):
    # 빈칸이면 좌표 저장
    if graph[i][j] == 0:
      blank.append((i, j))
      blank_num += 1

dfs(0, graph)

(풀이2) DFS를 이용한 성공 코드

1) 문제 해결 아이디어

9 * 9 스도쿠판에서 아래 조건 2개를 만족하면서 빈칸에 숫자를 모두 채운 결과를 출력하는 문제다. 스도쿠 문제는 전형적인 백트래킹 문제로 DFS를 이용하여 풀 수 있다.

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

<동작 과정>

1. 스도쿠 정보 입력 및 필요 변수 생성

blank: 빈칸의 좌표를 담기 위한 리스트

blank_num: 빈칸 개수

find: 정답 찾음 여부(플래그)

2. dfs 호출

3. 정답을 찾았으면 바로 종료(이게 없으면 모든 정답을 출력하게 되는 문제가 생김!!!)

4. 빈칸을 다 채웠으면 정답 출력, 정답 찾음(find)를 True로 변경 후 종료

5. depth번째 빈칸 좌표에 들어갈 후보 숫자 고르기

5-1. 후보 숫자(target)을 1 ~ 9 로 초기화

5-2. 가로줄, 세로줄에 있는 후보 숫자 제거

5-3. 굵은선 3*3 정사각형에 있는 후보 숫자 제거

6. 후보 숫자(target) 중에 빈칸에 들어갈 숫자 선택하기

6-1. 선택한 숫자 스도쿠(graph)에 쓰기

6-2. depth + 1로 인자를 넘겨 dfs 호출

6-3. 6-1에서 썼던 스도쿠 값을 0으로 원상복귀

 

2) 소스코드

import sys

# DFS
def dfs(depth):
  global find
  # 정답 찾았으면 종료
  if find:  return
  # 빈 칸을 다 채우면
  if depth == blank_num:
    for i in graph:
      print(*i)
    find = True  # 정답 찾음으로 변경
    return
  # 빈 칸을 다 채우지 못했으면
  x, y = blank[depth]  # depth번째 빈칸 좌표
  target = {1, 2, 3, 4, 5, 6, 7, 8, 9}  # 넣을 수 있는 후보 숫자
  # 1. 가로줄, 세로줄에 있는 숫자 후보에서 제거
  for i in range(9):
    target.discard(graph[x][i])  # 가로줄
    target.discard(graph[i][y])  # 세로줄  
  # 2. 굵은 선 3*3 정사각형 칸에 있는 수 후보에서 제거
  for i in range(3):
    for j in range(3):
      target.discard(graph[(x // 3) * 3 + i][(y // 3) * 3 + j])   
  # 후보 숫자 중에 선택하기
  for i in target:
    graph[x][y] = i  # 선택한 숫자 쓰기
    dfs(depth + 1)
    graph[x][y] = 0  # 원상복귀

# 9 * 9 스도쿠(0: 빈칸)
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(9)] 
blank = []     # 빈칸들 좌표
blank_num = 0  # 빈칸 개수
find = False   # 정답 찾음 여부

# 빈 칸 찾기
for i in range(9):
  for j in range(9):
    # 빈칸이면 좌표 저장
    if graph[i][j] == 0:
      blank.append((i, j))
      blank_num += 1
dfs(0)