백준 2580) 스도쿠 (골드.4)

 

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

2580번: 스도쿠

 

 

문제는 스도쿠 규칙과 똑같다. 가로 세로 9 사이즈의 보드에서 이루어진다. 

1) 가로열에 중복되는 숫자가 없을 것

2) 세로열에 중복되는 숫자가 없을 것 

3) 3*3 삼각형 안에 중복되는 숫자가 없을 것 

4) 여러 케이스가 있는 경우 하나의 케이스만 출력할 것 

 

가장 처음에 했던 코드는 다음과 같은데 잘못 했던 것이 조건당 하나의 빈칸만 있다고 생각하고 여러개의 선택지가 있다는 것을 하나도 생각 못한 코드다. 😭 세상에 😭  당연히 실패 

from collections import deque
board = [[] for _ in range(9)]

location = deque()
for i in range(9):
    numbers = list(map(int, input().split()))
    for j in range(9):
        if numbers[j] == 0:
            location.append((i, j))
    board[i].extend(numbers)
number = set([1, 2, 3, 4, 5, 6, 7, 8, 9])

while location:
    i, j = location.pop() 
    # 가로열 검사 
    r = number - set(board[i])
    if len(r) == 1:
        board[i][j] = list(r)[0]
        continue

    # 세로열 검사 
    c = set()
    for k in range(9):
        c.add(board[k][j])
    c = number - c
    if len(c) == 1:
        board[i][j] = list(c)[0]
        continue

    # 박스 검사 
    box = set()
    for a in range((i//3)*3, (i//3*3) + 3):
        for b in range((j//3)*3, (j//3)*3 +3):
            box.add(board[a][b])
    box = number - box
    if len(box) == 1:
        board[i][j] = list(box)[0]
        continue

    # 공통 필요인자 검사해서 채워넣기 
    possible = list(r & c & box)
    if len(possible) == 1:
        board[i][j] = possible[0]
        continue

    # 아직 정확한 필요인자 모르면 다시 추가 
    location.appendleft((i, j))

for i in range(9):
    for j in range(9):
        print(board[i][j], end=' ')
    print()

 

 

그 다음으로 시도한 방법은 dfs를 이용해서 빈칸에 1~10까지 돌며 숫자를 넣을 수 있는 올바른 케이스를 찾아내고 dfs를 다시 탐색하는 코드를 구성했다. 그런데 이 코드부터 82%까지 가서 계속해서 시간초과가 났다 😭

global board, isFinished
board = []
location = []
for i in range(9):
    board.append(list(map(int, input().split())))
    for j in range(9):
        if board[i][j] == 0:
            location.append((i, j))

def isPossible(i, j , num):
    global board
    for a in range(9):
        # 가로열 검사 
        if num == board[i][a]:
            return False
        # 세로열 검사 
        if num == board[a][j]:
            return False
    # 박스 검사 
    row = (i//3)*3
    column = (j//3)*3
    for a in range(row, row + 3):
        for b in range(column, column +3):
            if board[a][b] == num : 
                return False
    return True

def dfs(idx):
    global isFinished
    if idx == len(location):
        isFinished = True
        return 
    i, j = location[idx]
    for num in range(1, 10):
        if isPossible(i, j, num):
            board[i][j] = num 
            dfs(idx + 1)
            if isFinished:
                return 
            board[i][j] = 0 
    return 

isFinished = False
dfs(0)
for i in range(9):
    for j in range(9):
        print(board[i][j], end=' ')
    print()

 

 

코드를 수정해서 1~10까지 모두 돌지 않고 넣는 것이 가능한 숫자를 찾아서 넣을 수 있도록 했는데 역시나 위와 똑같기 때문에 82%에서 시간초과 😭

global board, isFinished
board = []
location = []
for i in range(9):
    board.append(list(map(int, input().split())))
    for j in range(9):
        if board[i][j] == 0:
            location.append((i, j))

def isPossible(i, j):
    possible_num = [1,2,3,4,5,6,7,8,9]
    global board
    for a in range(9):
        # 가로열 검사 
        if board[i][a] in possible_num:
            possible_num.remove(board[i][a])
        # 세로열 검사 
        if board[a][j] in possible_num:
            possible_num.remove(board[a][j])
    # 박스 검사 
    row = (i//3)*3
    column = (j//3)*3
    for a in range(row, row + 3):
        for b in range(column, column +3):
            if board[a][b] in possible_num : 
                possible_num.remove(board[a][b])
    return possible_num

def dfs(idx):
    global isFinished
    if idx == len(location):
        isFinished = True
        return 
    i, j = location[idx]
    possible_num = isPossible(i, j)
    for num in possible_num:
        board[i][j] = num 
        dfs(idx + 1)
        board[i][j] = 0 
    return 

isFinished = False
dfs(0)
for i in range(9):
    for j in range(9):
        print(board[i][j], end=' ')
    print()

 

 

 

조금 더 수정해서 결과가 나오지 않은 상태에서만 다음 케이스를 진행하도록 했지만 역시나 사실상 이전 코드와 똑같기 때문에 82%에서 시간초과 😭

global board, isFinished
board = []
location = []
for i in range(9):
    board.append(list(map(int, input().split())))
    for j in range(9):
        if board[i][j] == 0:
            location.append((i, j))

def isPossible(i, j):
    possible_num = [1,2,3,4,5,6,7,8,9]
    global board
    for a in range(9):
        # 가로열 검사 
        if board[i][a] in possible_num:
            possible_num.remove(board[i][a])
        # 세로열 검사 
        if board[a][j] in possible_num:
            possible_num.remove(board[a][j])
    # 박스 검사 
    row = (i//3)*3
    column = (j//3)*3
    for a in range(row, row + 3):
        for b in range(column, column +3):
            if board[a][b] in possible_num : 
                possible_num.remove(board[a][b])
    return possible_num
    
isFinished = False
def dfs(idx):
    global isFinished
    if isFinished:
        return 
    if idx == len(location):
        for i in board:
            print(*i)
        isFinished = True
        exit() 
    i, j = location[idx]
    possible_num = isPossible(i, j)
    for num in possible_num:
        board[i][j] = num 
        dfs(idx + 1)
        if not isFinished:
            board[i][j] = 0 
    return 

dfs(0)

 

 

 

그래서 검색찬스를 이용해서 이와 같은 방법 아니라면 어떻게 풀었는지 검색해보니, 백트래킹을 이용하기는 하는데 매번 열에서 넣을 수 있는 수를 돌아가면서 찾는 것이 아닌, 애초에 행, 열, 박스를 대상으로 각 배열의 인덱스 값의 존재여부를 2차원 배열로 만들어놓고 값이 True면 이미 있다는 의미이므로 진행하지 않고, 값이 False인 경우에 없다는 의미이므로 값을 사용하고 탐색할 수 있도록 하였다!

 

다음과 같이 코드를 수정하여 드디어 성공!

global board
board = []
location = []
check_row = [[False]*10 for _ in range(9)]
check_col = [[False]*10 for _ in range(9)]
check_box = [[False]*10 for _ in range(9)]
for i in range(9):
    board.append(list(map(int, input().split())))
    for j in range(9):
        if board[i][j] == 0:
            location.append((i, j))
        else :
            check_row[i][board[i][j]] = True
            check_col[j][board[i][j]] = True
            check_box[(i//3)*3 + j//3][board[i][j]] = True

def fill_board(idx):
    if idx == len(location):
        for i in board:
            print(*i)
        return True
    i, j = location[idx]
    for a in range(1, 10):
        if check_row[i][a] == False and check_col[j][a]==False and check_box[(i//3)*3 + j//3][a] == False:
            check_row[i][a] = check_col[j][a] = check_box[(i//3)*3 + j//3][a] = True
            board[i][j] = a 
            if fill_board(idx + 1):
                return True
            board[i][j] = 0 
            check_row[i][a] = check_col[j][a] = check_box[(i//3)*3 + j//3][a] = False
    return False

fill_board(0)

 

 

위의 코드로 드디어 성공!

 

 

 

(참고한 사이트) -> 설명이 자세히 되어있는 다음의 블로그를 참고하여 문제를 해결할 수 있었다!😭

https://hazung.tistory.com/129

[알고리즘] 백준 2580 스도쿠 / pyhton, 백트랙킹