[백준] 2239번 스도쿠 _ Python

2024. 1. 27. 17:05·Algorithms/Brute Fource

[초기 접근 방법]

스도쿠의 조건
    : 행, 열, 네모칸 모두 1가지 숫자만 있는 것

 

기본적으로 완전탐색

     - 백트래킹으로 넣었다 뺐다 하면 단축되지 않을까?
     - k 값은 스도쿠 값으로, range(1, 10)으로 설정해줘야 함

 

     - 백트래킹의 종료 조건

          → 스도쿠의 마지막 빈 칸이 채워졌을 때 종료한다.

 

 

[생각]

1) 인덱스 3*3 구역의 스도쿠 구역 체크할 때 인덱스 설정이 틀려서 20분을 썼다..

 

2) 그리고 한 가지 유의할 점이

스도쿠의 빈 칸의 값이 1~9 모두 유효하지 않을 때는,

이전 값이 틀린 것이므로 빠르게 return을 하여 해당 스도쿠의 빈 칸 dfs()를 끝내준다.

 

3) 아니면 스도쿠 빈 칸에 대한 1~9 check()를 반복문 안에서 하는 것이 아니라

dfs() 함수 첫번째에서 check()를 해주는 방법 또한 있다.

 

4) 추가로 시간복잡도 측면에서 효율적인 풀이는

스도쿠 빈 칸 좌표들을 튜플로 저장한 후, 해당 좌표들에 대해서만 dfs()를 하는 방법도 있을 수 있다.

 

 

[코드]

# 풀이 시간 : 1시간
# 시간복잡도 : O(9*9*9 - X)
# 공간복잡도 : O(9*9)
# 참고 : -

lst = [list(map(int, input())) for _ in range(9)]
cnt = 0

def check(row, col, num):
    for i in range(0, 9):
        if lst[row][i] == num:
            return False

    for i in range(9):
        if lst[i][col] == num:
            return False

    quotR = row // 3
    quotC = col // 3

    for i in range(3):
        for j in range(3):
            if lst[3*quotR+i][3*quotC+j] == num:
                return False

    return True


def dfs(R, C):
    global cnt
    global finalX, finalY
    if finalX == R and finalY == C:
        for i in range(9):
            for j in range(9):
                print(lst[i][j], end="")
            print()
        exit()


    for i in range(9):
        for j in range(9):
            # 빈 칸 넣기
            if lst[i][j] == 0:
                for k in range(1, 10):
                    if check(i, j, k):
                        lst[i][j] = k
                        dfs(i, j)
                        lst[i][j] = 0

                    # 1~9 까지 모두 안 되었을 경우, 이전 lst[i][j] 값을 다른 값을 넣어줘야 함
                    # cf. check[9] == True 일 때, final까지 계속 dfs 탐색함.
                    if k == 9:
                        return


finalX = 0
finalY = 0
for i in range(9):
    for j in range(9):
        if lst[i][j] == 0:
            finalX = i
            finalY = j

dfs(0, 0)
저작자표시 (새창열림)

'Algorithm > Brute Fource' 카테고리의 다른 글

[백준] 1079번 마피아 _ Python  (0) 2024.01.29
[백준] 18111번 마인크래프트 _ Python  (0) 2024.01.16
[백준] 2422번 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 _ Python  (1) 2023.11.16
[백준] 15721번 번데기 _ Python  (1) 2023.11.14
[백준] 1548번 부분 삼각 수열 _ Python  (0) 2023.11.10
'Algorithms/Brute Fource' 카테고리의 다른 글
  • [백준] 1079번 마피아 _ Python
  • [백준] 18111번 마인크래프트 _ Python
  • [백준] 2422번 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 _ Python
  • [백준] 15721번 번데기 _ Python
wch_t
wch_t
  • wch_t
    끄적끄적(TIL)
    wch_t
  • 글쓰기 관리
  • 전체
    오늘
    어제
    • 분류 전체보기 (171)
      • Architecture (0)
      • Algorithm (67)
        • Math (5)
        • Simulation (1)
        • Data Structure (4)
        • DP (7)
        • Brute Fource (10)
        • Binary Search (6)
        • Greedy (2)
        • Graph (11)
        • Mst (1)
        • Shortest path (10)
        • Two Pointer (1)
        • Tsp (3)
        • Union Find (2)
        • Mitm (1)
      • CS (2)
        • 데이터베이스 (5)
        • 네트워크 (5)
      • DB (6)
      • DevOps (17)
        • AWS (9)
        • Docker (1)
        • CI-CD (5)
      • Error (1)
      • Project (0)
        • kotrip (0)
      • Spring (59)
        • 끄적끄적 (5)
        • 기본 (9)
        • MVC 1 (7)
        • MVC 2 (11)
        • ORM (8)
        • JPA 1 (7)
        • JPA 2 (5)
        • Spring Data Jpa (7)
      • Test (2)
      • TIL (6)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    docker: not found
    애플
    form_post
    TempTable
    Sxssf
    spring-cloud-starter-bootstrap
    aws secrets manager
    백준 3015 파이썬
    docker
    백준 17299 파이썬
    response_mode
    apache poi
    Jenkins
    백준 17289 파이썬
    spring-cloud-starter-aws-secrets-manager-config
    view algorithm
    Merge
    scope
  • 최근 댓글

  • hELLO· Designed By정상우.v4.10.3
wch_t
[백준] 2239번 스도쿠 _ Python
상단으로

티스토리툴바