[Python/코테] 백준 2239 스도쿠

2239 스도쿠

문제 및 조건 설명: https://www.acmicpc.net/problem/2239

알고리즘 설계

💡idea.

각 칸마다 가능한 경우를 확인해야 한다. 특정 칸에서 막힌다면 그 직전에 채운 칸을 바꾸어야 한다. 조건에 맞지 않으면 다시 돌아가서 탐색을 시작한다는 점에서 백트래킹을 활용할 수 있음을 알 수 있다.

 

🎲step.

1. 함수

빈 좌표를 찾아, 값을 넣어보고 다음 칸에도 계속 넣어본다.

 

2. Base condition

빈 좌표가 없다면 종료된다.

 

3. 재귀

빈 좌표에 어떤 값을 넣고, 다음 빈 좌표에 값을 채우기 위해 재귀를 사용한다.

def func():
    # 빈 좌표를 찾는다.
    
    # 빈 좌표가 없다면 True 반환
    # 빈 좌표가 있다면 
        for i in range(1, 10):
            # 빈 좌표에 i값이 들어갈 수 있을지 검사하다.
                p[x][y] = i # 값을 넣어본다.
                if func():  # 남은 빈 좌표들을 계속 채운다.
                    return True  # 정상 종료
                p[x][y] = 0  # 한 곳이라도 넣을 수 없다면 다음 값(i+1)을 넣어본다.
        return False

알고리즘 구현

출처: https://gaza-anywhere-coding.tistory.com/42

p = [list(map(int, input())) for _ in range(9)]


def find_empty():
    for i in range(9):
        for j in range(9):
            if p[i][j] == 0:
                return i, j
    return None, None           # 다 채워져있을 때


def valid(x, y, val):       # [x][y]에 val숫자를 넣을 수 있는가?
    for i in range(9):
        if p[x][i] == val:  # 해당 행에 이미 val가 사용되었으면,
            return False
        if p[i][y] == val:  # 해당 열에 이미 val가 사용되었으면
            return False

    col = x // 3 * 3  # 현재의 (x, y)가 속한 3x3 사각형의 왼쪽 상단 좌표
    row = y // 3 * 3
    for i in range(3):
        for j in range(3):
            if p[col+i][row+j] == val:
                return False
    return True


def func():
    x, y = find_empty()
    if y is None:
        return True
    else:
        for i in range(1, 10):
            if valid(x, y, i):
                p[x][y] = i
                if func():  # 해당 위치에 값 i를 넣을 수 있다면
                    return True  # 종료
                p[x][y] = 0  # 넣을 수 없다면 다음 값(i+1)을 넣어본다.
        return False


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

 

나다어

• 재귀 함수의 역할을 생각해내는 것이 어려웠다. 빈 좌표를 찾아 가능한 숫자를 대입해보고, 다음 칸으로 넘어가는 역할이다. 백트래킹이므로 각 경우(함수가 실행될 때)마다 가지를 가지게 된다고 이해하면 쉽다.
• 조건을 확인하기가 복잡했다. 이 문제는 9*9로 칸이 정해져 있으니 직접 대입하여 확인해도 괜찮다. 여러 번 확인하게 되니 따로 함수를 정의하는 것도 좋은 방법이다.
• 정말 모르겠으면 종료 조건을 명확히 해 보면서 과정을 찾아가는 것도 좋아 보인다..