카테고리 없음

[백준/파이썬][Gold IV] 스도쿠 - 2239

난쟁이 개발자 2024. 12. 19. 23:13
반응형

[Gold IV] 스도쿠 - 2239

문제 링크

성능 요약

메모리: 142488 KB, 시간: 5592 ms

분류

백트래킹, 구현

제출 일자

2024년 12월 19일 22:55:24

문제 설명

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

입력

9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

출력

9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

풀이

def is_valid(num, row, col) :
    # 1. 현재 위치에 num이 들어갈 수 있는지 검사
    return not (in_row(num, row) or in_col(num, col) or in_box(num, row, col))

def in_row(num, row) :
    # 2. 해당 행에 num이 있는지 확인
    return num in board[row]

def in_col(num, col) :
    # 3. 해당 열에 num이 있는지 확인
    return num in (board[i][col] for i in range(9))

def in_box(num, row, col) :
    # 4. 현재 위치의 3x3 박스에 num이 있는지 확인
    box_row = (row//3) * 3
    box_col = (col//3) * 3

    for i in range(box_row, box_row + 3) :
        for j in range(box_col, box_col + 3) :
            if board[i][j] == num :
                return True

    return False

def find_empty_position() :
    # 5. 스도쿠 보드에 비어있는 위치 반환
    for i in range(9) :
        for j in range(9) :
            if board[i][j] == 0 :
                return i, j
    return None

def solve() :
    # 6. 비어 있는 위치에 가능한 숫자를 넣어가며 스도쿠 해결
    empty_pos = find_empty_position()
    # 7. 빈 칸이 없으면 스도쿠가 해결된 것으로 간주
    if not empty_pos :
        return True
    row, col = empty_pos
    for num in range(1, 10) :
        if is_valid(num, row, col) :
            board[row][col] = num
            if solve() :    # 8. 다음 빈 칸으로 재귀적으로 탐색
                return True
            board[row][col] = 0 # 9. 가능한 숫자가 없으면 원래의 0으로 되돌림
    return False

board = [list(map(int, input())) for _ in range(9)]
solve()
for i in board :
    print(*i, sep='')

대부분 조합을 찾는 문제는 백트래킹 문제라고는 하는데 도저히 익숙해지지 않는다.

1. is_valid(num, row, col)

def is_valid(num, row, col) :
    # 1. 현재 위치에 num이 들어갈 수 있는지 검사
    return not (in_row(num, row) or in_col(num, col) or in_box(num, row, col))
  • 특정 숫자(num)가 주어진 위치(row, col)에 들어갈 수 있는지 확인하는 함수입니다.
  • 세 가지 조건을 검사합니다:
    1. 같은 행에 num이 있는지 확인: in_row(num, row)
    2. 같은 열에 num이 있는지 확인: in_col(num, col)
    3. 같은 3x3 박스에 num이 있는지 확인: in_box(num, row, col)
  • 이 조건 중 하나라도 위배되면 False, 모두 만족하면 True를 반환합니다.

2. in_row(num, row)

def in_row(num, row) :
    # 2. 해당 행에 num이 있는지 확인
    return num in board[row]
  • 특정 숫자 num이 해당 행(row)에 있는지 확인합니다.
  • return num in board[row]에서 board[row]는 행 데이터를 가져오며, Python의 in 키워드를 사용해 num의 존재를 확인합니다.

3. in_col(num, col)

def in_col(num, col) :
    # 3. 해당 열에 num이 있는지 확인
    return num in (board[i][col] for i in range(9))
  • 특정 숫자 num이 해당 열(col)에 있는지 확인합니다.
  • 열 데이터는 board[i][col]를 통해 각 행의 col 번째 요소를 가져옵니다.
  • 리스트 컴프리헨션을 사용하여 열 데이터를 생성한 후, num이 있는지 검사합니다.

4. in_box(num, row, col)

def in_box(num, row, col) :
    # 4. 현재 위치의 3x3 박스에 num이 있는지 확인
    box_row = (row//3) * 3
    box_col = (col//3) * 3

    for i in range(box_row, box_row + 3) :
        for j in range(box_col, box_col + 3) :
            if board[i][j] == num :
                return True

    return False
  • 현재 위치(row, col)가 속한 3x3 박스에서 num이 있는지 확인합니다.
  • 3x3 박스의 시작 좌표를 계산:
    • box_row = (row // 3) * 3: 행 기준으로 3의 배수인 시작점.
    • box_col = (col // 3) * 3: 열 기준으로 3의 배수인 시작점.
  • 이 박스의 모든 셀을 순회하며 num이 있는지 확인합니다.

5. find_empty_position()

def find_empty_position() :
    # 5. 스도쿠 보드에 비어있는 위치 반환
    for i in range(9) :
        for j in range(9) :
            if board[i][j] == 0 :
                return i, j
    return None
  • 보드에서 아직 숫자가 채워지지 않은 빈 칸(값이 0인 위치)을 찾습니다.
  • 위에서부터 아래로, 왼쪽에서 오른쪽으로 순회하며 처음으로 발견한 빈 칸의 좌표를 반환합니다.
  • 더 이상 빈 칸이 없다면 None을 반환합니다.

6. solve()

def solve() :
    # 6. 비어 있는 위치에 가능한 숫자를 넣어가며 스도쿠 해결
    empty_pos = find_empty_position()
    # 7. 빈 칸이 없으면 스도쿠가 해결된 것으로 간주
    if not empty_pos :
        return True
    row, col = empty_pos
    for num in range(1, 10) :
        if is_valid(num, row, col) :
            board[row][col] = num
            if solve() :    # 8. 다음 빈 칸으로 재귀적으로 탐색
                return True
            board[row][col] = 0 # 9. 가능한 숫자가 없으면 원래의 0으로 되돌림
    return False
  • 재귀적으로 빈 칸에 숫자를 채우며 스도쿠를 해결하는 핵심 함수입니다.
  1. find_empty_position()으로 빈 칸을 찾습니다.
    • 빈 칸이 없으면(empty_pos is None) 스도쿠가 해결된 상태이므로 True를 반환합니다.
  2. 빈 칸이 있으면 1부터 9까지의 숫자를 차례로 시도합니다:
    • is_valid(num, row, col)로 현재 숫자가 유효한지 검사.
    • 유효하다면 보드에 숫자를 채웁니다(board[row][col] = num).
    • 이후 재귀적으로 solve()를 호출하여 다음 빈 칸을 해결.
  3. 재귀 호출에서 True가 반환되면 스도쿠 해결 성공.
    • 그렇지 않으면(False 반환 시) 잘못된 숫자를 채운 것이므로 board[row][col] = 0으로 되돌립니다.
  4. 모든 경우의 수를 시도했는데도 해결되지 않으면 False 반환.

7. 실행 부분

board = [list(map(int, input())) for _ in range(9)]
solve()
for i in board :
    print(*i, sep='')
  1. board는 사용자 입력을 통해 9x9 크기의 스도쿠 보드로 초기화됩니다.
    • 각 행의 숫자를 공백 없이 입력받고, 이를 정수 리스트로 변환.
    • 예: 530070000 → [5, 3, 0, 0, 7, 0, 0, 0, 0]
  2. solve() 함수로 스도쿠를 해결.
  3. 해결된 보드를 출력:
    • print(*i, sep='')로 각 행을 출력하며, 숫자 사이에 공백을 넣지 않음.
반응형