[백준-파이썬] 2239: 스도쿠, 2580: 스도쿠

TMI 🤸‍♀️

싸피 자치회 회의 - 스터디를 하고 나니 좀 피곤했다. 스터디의 문제는 좀 어렵고 잘 이해가 안돼서ㅠㅠ 풀 문제를 찾다가 이 문제(2580)를 찾았다. 문제 보러 가기

문제를 읽다 보니 전에 비슷한 문제를 푼 생각이 났다. 바로 이 문제(2239)였다.

반 년 전에, 내가 세네 번째로 푼 백준 골드 문제였던 걸로 기억한다..! 추억의 문제 ><

다른 분의 블로그를 보면서 이해하고 풀었던 것 같다. 이 블로그에는 pypy뿐 아니라 python으로 통과하는 방법도 써 있어서 나도 다시 읽어봐야겠다.

풀이 ❤

1. 스도쿠에서 채워야 할 자리(0)들을 찾아서 blanks 리스트 안에 튜플로 저장한다.

2. blanks에 들어갈 값을 하나씩 찾는다.

2-1. 1~9 숫자를 썼는지 안 썼는지 체크할 check 리스트를 만든다. 처음에는 False로 세팅한다. 인덱스를 편하게 쓰려고 길이를 10으로 해줬다.

2-2. 그 값이 포함되는 가로, 세로의 값들을 확인한다. 값을 check에 반영한다. 예를 들어서 그 값을 포함하는 가로에 1이 있으면 check[1] = True로 해주는 것이다.

2-3. 그 값이 포함되는 작은 사각형의 값들도 확인한다.

2-4. 1~9의 숫자 중 False인 수를 해당 값에 넣는다. 

3. blanks를 다 봤으면, 완성된 스도쿠를 출력한다. 

4. 한 가지 경우만 출력하면 되므로, 일단 완성됐으면 end_flag를 True로 바꿔준다. 그러면 이제 dfs 함수에 들어왔을 때 end_flag가 True이면 리턴해준다. (백 트래킹)

2239 코드 👩‍💻

# https://dct-wonjung.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-%EC%8A%A4%EB%8F%84%EC%BF%A0 를 참고

def dfs(depth):  # 0이었던 것 중에 depth 번째 꺼를 채워줄 차례
    global end_flag

    if end_flag:  # 처음으로 스토쿠 완성 되었으면, 앞으로는 무조건 리턴
        return

    if depth == len(blanks):  # 스토쿠 완성
        end_flag = True
        for s in sdoku:
            print(''.join(map(str, s)))
        return

    ii, jj = blanks[depth]  # 채워야 할 빈 칸

    # 1~9 숫자 중 가로, 세로, 작은 사각형 안에 있는 숫자를 체크
    check = [True] + [False for _ in range(9)]
    for k in range(9):
        # 가로
        check[int(sdoku[ii][k])] = True  # 이미 1이어도 1로 해줘도 상관없고, 0이었으면 1로 바꿔주는 거
        # 세로
        check[int(sdoku[k][jj])] = True

    # 작은 사각형
    for k_i in range(3):
        for k_j in range(3):
            check[int(sdoku[(ii // 3) * 3 + k_i][(jj // 3) * 3 + k_j])] = True

    # print(ii,jj, check)
    # 가로, 세로, 작은 사각형에 없는 숫자를 대입하기
    for k in range(10):
        if check[k] == False:
            sdoku[ii][jj] = k
            dfs(depth + 1)
    sdoku[ii][jj] = '0'


sdoku = list(list(input()) for _ in range(9))
blanks = []  # 채워야 할 것들
end_flag = False
for i in range(9):
    for j in range(9):
        if int(sdoku[i][j]) == 0:
            blanks.append((i, j))
# print(blanks)
dfs(0)

2580번 코드 👩‍💻

2580번도 2239번과 입력만 다르고 거의 비슷해서! 그때 코드를 가져와서 이해해보고, 조금 수정했다..ㅎㅎ

'''
스도쿠
https://www.acmicpc.net/problem/2580
'''


def dfs(depth):  # 0이었던 것 중에 depth번째 꺼를 채워줄 차례
    global end_flag

    if end_flag:  # 처음으로 스토쿠 완성 되었으면, 앞으로는 무조건 리턴
        return

    if depth == len(blanks):  # 스토쿠 완성
        end_flag = True

        # 출력
        for s in sdoku:
            print(' '.join(map(str, s)))
        return

    ii, jj = blanks[depth]  # 채워야 할 빈 칸

    # 1~9 숫자 중 가로, 세로, 작은 사각형 안에 있는 숫자를 체크
    check = [True] + [False for _ in range(9)]
    for k in range(9):
        # 가로
        check[sdoku[ii][k]] = True  # 이미 1이어도 1로 해줘도 상관없고, 0이었으면 1로 바꿔주는 거
        # 세로
        check[sdoku[k][jj]] = True

    # 작은 사각형
    for k_i in range(3):
        for k_j in range(3):
            check[sdoku[(ii // 3) * 3 + k_i][(jj // 3) * 3 + k_j]] = True

    # 가로, 세로, 작은 사각형에 없는 숫자를 대입하기
    for k in range(10):
        if check[k] == False:
            sdoku[ii][jj] = k
            dfs(depth + 1)
    sdoku[ii][jj] = 0


sdoku = list(list(map(int, input().split())) for _ in range(9))
blanks = []  # 채워야 할 것들
end_flag = False
for i in range(9):
    for j in range(9):
        if sdoku[i][j] == 0:
            blanks.append((i, j))

dfs(0)