백준 2239번 파이썬 문제풀이(스도쿠)

---

이 문제 정말 킹받았다.. 구현하기도 힘들었고 백트래킹을 어떻게 잡아주어야 할지도 몰랐다. 약간의 힌트를 봤더니 중요한건 0의 위치를 튜플형식으로 저장한 후 0의 위치를 dfs를 도는 것이다. 그리고 0의 위치만큼 dfs를 돌아서 (물론 돌면서 백트래킹으로 행,열,3*3 스도쿠 조건을 검증해야함) 나오는 첫번째 스도쿠를 출력하면 된다. 

 

# 행검사
def row_check(r, c, num):
    for x in range(9):
        if c != x and num == sdoku[r][x]:
            return False
    return True


def col_check(r, c, num):
    # 열검사
    for x in range(9):
        if r != x and num == sdoku[x][c]:
            return False
    return True


def three_check(r, c, num):
    # 3x3 검사
    nc = (c // 3) * 3
    nr = (r // 3) * 3
    for x in range(3):
        for y in range(3):
            if r != nr + x and c != nc + y and sdoku[nr + x][nc + y] == num:
                return False
    return True


def dfs(depth, r, c, num):
    if depth > 0:
        # 행검사
        if not row_check(r, c, num):
            return
        # 열검사
        if not col_check(r, c, num):
            return
        # 3x3 검사
        if not three_check(r, c, num):
            return

    if depth >= len(zero_p):  # 만약 0의 개수에 도달 했다면
        for k in range(9):
            print(''.join(map(str, sdoku[k])))
        exit()

    nr, nc = zero_p[depth]  # 0의 좌표를 dfs를 돈다.
    for j in range(1, 9 + 1):
        sdoku[nr][nc] = j
        dfs(depth + 1, nr, nc, j)
        sdoku[nr][nc] = 0


sdoku = []
zero_p = [] # 2차원 9*9 리스트를 1차원적으로 생각하여 dfs를 돌기 때문에 좌표들을 튜플형식으로 넣는다.
for i in range(9):
    temp = list(map(int, input()))
    for j in range(len(temp)):
        if temp[j] == 0:
            zero_p.append((i, j))
    sdoku.append(temp)

dfs(0, 0, 0, 0)

 

어떤 코드를 봤는데 백트래킹 검사를 dfs를 돌면서 검사하는 것이아닌 애초에 dfs를 돌기전에 검사하는 코드가 있어서 공유한다. 나의 코드보다 더 빠르게 동작한다.

# 행검사
def row_check(r, num):
    for x in range(9):
        if num == sdoku[r][x]:
            return False
    return True


def col_check(c, num):
    # 열검사
    for x in range(9):
        if num == sdoku[x][c]:
            return False
    return True


def three_check(r, c, num):
    # 3x3 검사
    nc = (c // 3) * 3
    nr = (r // 3) * 3
    for x in range(3):
        for y in range(3):
            if sdoku[nr + x][nc + y] == num:
                return False
    return True


def dfs(depth):
    if depth >= len(zero_p):
        for k in range(9):
            print(''.join(map(str, sdoku[k])))
        exit()

    nr, nc = zero_p[depth]  # 리스트에서 하나씩 튜플로 꺼낸다.
    for j in range(1, 9 + 1):
    	#dfs를 돌기전에 검사하여 조건에 맞는 것만 dfs를 돈다
        if row_check(nr, j) and col_check(nc, j) and three_check(nr, nc, j):
            sdoku[nr][nc] = j
            dfs(depth + 1)
            sdoku[nr][nc] = 0


sdoku = []
zero_p = []  # 2차원 9*9 리스트를 1차원적으로 생각하여 dfs를 돌기 때문에 좌표들을 튜플형식으로 넣는다.
for i in range(9):
    temp = list(map(int, input()))
    for j in range(len(temp)):
        if temp[j] == 0:
            zero_p.append((i, j))  # 0의 좌표들을 저장한다.(1차원 리스트에 튜플로 저장)
    sdoku.append(temp)

dfs(0)