백준 2580 스도쿠 문제풀이

문제 

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

2580번: 스도쿠

 

 

 

 

문제 접근 방식

빈칸을 하나씩 순회하면서 숫자를 채워넣는 방식으로 구현을 했다.

숫자를 채워넣는 경우 1~9를 모두 채워넣는 방식이 아닌 현재 행, 열을 통해서 해당 행의 가능한 숫자, 해당 열에서 가능한 숫자 , 해당 그룹에서 가능한 숫자의 교집합을 통해서 가능한 숫자를 추렸다. 이후 가능한 숫자를 하나씩 넣고 다음 빈칸으로 넘어가는 방식으로 스도쿠를 풀었다.

 

 

코드

def cal_group(row,col):
    y=row//3
    x=col//3
    return 3*y+x

def dfs(index):
    if index== len(empty):
        # 모두 채워졌다면 출력
        for i in range(9):
            for j in range(9):
                print(board[i][j],end=' ')
            print()
        return True

    r,c=empty[index]
    group_num=cal_group(r,c)
    possible_nums=rows[r] & cols[c] & groups[group_num]

    for num in list(possible_nums):
        rows[r].remove(num)
        cols[c].remove(num)
        groups[group_num].remove(num)
        board[r][c]=num

        # 출력이 되었다면 True를 반환
        if dfs(index+1):
            return True

        #원상복구
        rows[r].add(num)
        cols[c].add(num)
        groups[group_num].add(num)
        board[r][c]=0

    return False

if __name__=='__main__':
    global board,empty,rows,cols,groups
    board=[]
    for _ in range(9):
        board.append(list(map(int,input().split())))

    empty=[]
    rows = [set([i for i in range(1,10)]) for _ in range(9)]
    cols = [set([i for i in range(1,10)]) for _ in range(9)]
    groups = [set([i for i in range(1,10)]) for _ in range(9)]

    # 빈칸의 위치 정보를 리스트에 저장
    for i in range(9):
        for j in range(9):
            if board[i][j]==0:
                empty.append((i,j))
            else:
                rows[i].remove(board[i][j])
                cols[j].remove(board[i][j])
                group_num=cal_group(i,j)
                groups[group_num].remove(board[i][j])

    dfs(0)

 

 

회고

 

파이썬에서 시간초과가 나서 pypy3 로 돌려서 코드가 맞는지만 확인해보았다.

상위 파이썬 문제 풀이를 보니 100ms 인거 보면 접근 방식을 다르게 해야되는 것 같다. 

다른 문제풀이는 어떻게 되어 있는지 확인하고 수정을 하겠다.