백준 2580 스도쿠 dfs python 차근 차근 정말 쉽게 설명한 풀이방법

백준 2580 스도쿠 게임을 python 으로 코딩하는 방법을 자세하게 설명을 드립니다. 스도쿠는 9개의 행과 9개의 열로 구성되어 있으며 인접하게 연결된 9개의 상자들에게 숫자 1부터 숫자 9까지 겹쳐지지 않도록 숫자를 배정하는 게임입니다.

백준 2580 스도쿠 python 문제 요약

백준 2580 스도쿠 문제는 가로로 9개의 단어에 숫자 1부터 숫자 9까지 모든 각 숫자들이 꼭 한 번씩 상자에 기록되어야 합니다. 또한 숫자 9개를 가로 3 행 세로 3 열의 정사각형으로 모아두고 9개의 숫자들을 꼭 1회 씩 배치하는 게임입니다.

스도쿠 python 코딩을 완료한 후에 디버깅은 필수입니다. 알고리즘 코딩을 진행하면서 잊어버리지 말고 꼭 아래의 데이터들을 입력해서 각 데이터를 처리하는 메서드마다 print( )를 출력해서 입력받은 데이터셋과 메서드 내부에서 사용하는 데이터셋이 동일한지 자주 확인해 주어야 합니다.

네카라쿠배 회사의 코딩 시험은 보통 3시간 동안에 3 문제 정도를 풀어야 합니다. 시험에 응시하여 코딩을 진행 하는 과정에서 가장 중요한 것은 문제의 의도와 조건과 변수들을 꼼꼼하게 파악하고 python 코드의 변수와 함수로 빠뜨리지 않고 꼭 구현을 해주어야 한다는 점입니다.

테스트용 입력 데이터

0 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
0 6 0 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7
8 0 4 9 1 3 5 0 6
5 9 6 8 2 0 4 1 3
9 1 7 6 5 2 0 8 0
6 0 3 7 0 1 9 5 2
2 5 8 3 9 4 7 6 0

테스트 결과 확인용 출력 데이터

1 3 5 4 6 9 2 7 8
7 8 2 1 3 5 6 4 9
4 6 9 2 7 8 1 3 5
3 2 1 5 4 6 8 9 7
8 7 4 9 1 3 5 2 6
5 9 6 8 2 7 4 1 3
9 1 7 6 5 2 3 8 4
6 4 3 7 8 1 9 5 2
2 5 8 3 9 4 7 6 1

코딩 테스트를 잘 보려면 무엇을 준비해야 할까?

코딩 테스트를 온라인으로 풀어보면 보통 3시간 안에 3개의 python 언어로 알고리즘 문제를 해결하는 코딩을 완성하고 디버깅까지 완료 시켜야 합니다. 코딩 테스트에서 문제의 정답을 맞추는 것도 상당히 힘들고 피로한 일입니다.

평일에는 주로 저녁 시간에 python 알고리즘 코딩을 하고 있습니다. 문제 풀이에서 가장 어려운 점은 저녁이라서 졸리다는 점입니다. 문제의 의도를 이해하여 python 코드들을 작성하고 한 시간 이내에 디버깅도 완료하고 코드 실행 속도 최적화 작업을 완료하여 목표 시간 이내에 문제를 해결하는 것은 참 어려운 일입니다.

제가 먼저 시행착오를 거치면서 본 포스팅에 자세하게 정리한 노하우를 이용하면 쉽게 공부하실 수 있습니다. 수많은 시행착오를 거치면서 한 문제를 풀기 위해서 최소한 8번 이상 python 코드를 작성하고 디버깅을 진행하면서 정답 코딩을 완성해왔습니다. 코딩 테스트의 가장 기본인 문제들과 풀이 방법과 완벽하게 에러 없이 동작하는 코드를 아래 포스팅에서 확인해 보실 수 있습니다.

백준 3190 뱀 문제 python 풀이 방법 보러가기

백준 5917 문제 python 문제 풀이 방법 바로 보러가기

스도쿠 코드를 이해를 위해 미리 알아야 할 코드

오늘도 또상님의 스도쿠 코드를 이해하기 위해서 머리털을 쥐어 뜯고 있습니다. 정말 저자로 부터 일대일 개인 과외라도 받고 싶습니다. ch[][][] 은 3차원 배열로서 스도쿠에서 빙고가 완성되었는지 판단하기 위해서 사용됩니다.

백준 2580 스도쿠 문제에서 빙고가 완성되는 경우는 아래와 같이 3가지 경우가 있습니다.

가로로 인접한 9개의 숫자로 구성된 행이 1부터 9까지 전부 한번씩 채워져 있는 경우가 있습니다.

세로로 인접한 9개의 숫자로 구성된 열에 1 부터 9까지 전부 숫자들이 채워져 있고 그 숫자들은 1 부터 9까지 꼭 한번 씩 배치되어 있습니다.

가로 3행 세로 3열의 정사각형 배열 안에 1부터 9까지의 숫자가 꼭 한번씩 배치되어 있습니다.

아래 코드를 해석해보자면 ch[0][i][sudoku[i][j]] 배열은 인덱스 0은 3가지 경우 중에서 첫번째 케이스를 의미하고 i 인덱스는 배열에서 행의 번호를 의미하여 sudoku[i][j] 는 사용자가 입력한 데이터 셋에서 i 번째 행 j번째 열에 해당하는 숫자 값을 의미합니다. 즉 sudoku[i][j] 는 어떠한 정수 값을 뜻하게 됩니다.

다시 ch[0][i][sudoku[i][j]] = 1 의 뜻을 재 해석해 보겠습니다. ch[0][i][sudoku[i][j]] 에서 i 번째 행에 존재하는 0열부터 9열까지의 원소 중에서 sudoku[i][j] 라는 숫자에 해당하는 열의 원소가 1로 설정되었다는 의미입니다. 약간 의역하자면 i번째 행의 sudoku[i][j] 열은 점유되었다고 표시가 되었는데 숫자 1이 배정된 것은 점유되었다는 사실을 마킹한 것이라고 해석할 수 있습니다.

    ch[0][i][sudoku[i][j]] = 1
    ch[1][j][sudoku[i][j]] = 1
    ch[2][3 * (i // 3) + j // 3][sudoku[i][j]] = 1

데이터 입력 코드 분석

코딩 테스트에서 가장 일반적으로 많이 사용하는 방식으로 9행 9열의 데이터를 읽어 들이기 위해서 사용하는 코드입니다. 핵심은 map(int,readl().split() 이라는 코드가 입력된 단어들을 작은 따옴표로 묶어놓은 단어들의 리스트로 일단 입력되었다가 map( int, …) 메서드가 적용되면서 작은 따옴표가 사라지면서 정수형으로 변수가 변경됩니다.

print( )해서 살펴보면 작은 따옴표로 묶어두었던 캐릭터 타입의 변수가 정수로 변경되었음을 알 수 있습니다. 이대로 사용할 수는 없습니다. DFS( ) 메서드 내부에서 정수형으로 된 변수들을 활용해서 숫자가 1 부터 9까지 모두 사용되었는지 파악하기 위해서 활용해야 합니다. 따라서, 변수의 타입은 정수형으로 변경해두어야 나중에 이용하기에 편리합니다.

sudoku = [list(map(int, readl().split())) for _ in range(9)]

sudoku는 9행 9열의 배열로서 사용자가 입력한 정수 값이 채워진 입력 데이터로서 작성하는 코드 내부에서 지속적으로 활용되는 것입니다.

DFS( ) 메서드 분석

백준 2580 스도쿠 문제는 dfs 알고리즘을 이용해서 해결하는 문제입니다. 이름에서 의미하는 바와 같이 트리 구조의 자료 구조에서 트리의 깊이 우선으로 탐색하는 방식으로 자료를 순회하게 됩니다.

시간이 오래 걸리지만 코드 작성 측면에서는 재귀 호출을 이용하므로 코딩 량은 줄어들게 됩니다. 하지만 exit 조건을 추가하지 않으면 영원히 재귀 호출 루프에 빠져서 컴퓨터가 먹통이 될 우려가 있습니다. 알고리즘 코딩 테스트에서는 dfs 구조의 알고리즘들이 자주 출제되므로 충분히 연습할 필요는 있습니다.

위에서 sudoku 9행 9열의 배열에 저장한 입력 데이터에서 값이 비어있는 0 이 설정된 데이터의 갯수를 zero_cnt 라고 정의하고 기본 코드에서 카운트 해줍니다.

DFS( level, idx ) 메서드에 level 입력값과 idx 입력값을 최초에는 DFS( 0, 0 ) 으로 설정합니다. level 이라는 변수는 고정된 상수 값이 아느라 DFS( ) 메서드 내부에서 동작하면서 재귀 호출을 할 때 DFS ( level +1, idx + 1) 로 값이 숫자가 1 만큼 증가하여 입력됩니다. idx 도 마찬가지로 상수가 아니라 코드 내부에서 재귀 호출을 할 때 idx + 1 만큼 증가시켜서 입력해 줍니다.

아래 코드는 level 과 0 값의 갯수가 같으면 sudoku 배열의 값을 출력해주고 종료되는 구문입니다.

if level == zero_cnt:
	if checkSudoku():
		printSudoku()
		exit(0)
	return

DFS( ) 메서드 호출 전 사전 준비 작업

DFS( )를 호출하기 전에 sudoku[i][j] 배열값 자체가 0 인 원소의 (i, j) 좌표를 별도의 리스트인 zeros 에 추가해 둡니다.

sudoku[i][j] 가 0이 아니라 다른 값이 주어져 있다면 각 체크 매트릭스의 i 번째 행의 sudoku[i][j] 번째 열이 점유되었음을 의미하기 위하여 ch[0][i]sudoku[i][j]]=1 로 값을 설정합니다.

두번째 체크매트릭스에는 각 열의 어느 원소가 sudoku[i][j] 로 점유되었는지 표기하기 위하여 1을 설정합니다. 즉 ch[1][j][sudoku[i][j]] = 1이라고 설정하게 되는데 이렇게 표시하는 이유는 스도쿠 게임 규칙 중에서 새로로 9개의 숫자가 전부 배치하면 빙고가 되기 때문입니다.

가장 중요한 이유는 메모리 사용량을 줄여서 스도쿠 판에서 비어있는 칸을 빨리 찾기 위함입니다. 연산의 복잡도가 O(1) 로서 일일이 확인하는 것보다 빠르게 찾을 수 있습니다.

특히 아래 구문을 활용해서 가로 3행 세로 3행에 값이 배치가 되었는지 구분하기 위해서 마킹하는 역할을 수행합니다.

ch[2][3 * (i // 3) + j // 3][sudoku[i][j]] = 1

이제 본격적으로 dfs( ) 메서드 구현방식에 대해서 알아보겠습니다.

DFS( ) 메서드 구현하기

백준 2580 스도쿠 python 프로그래밍의 가장 핵심 구문에 해당합니다. 그만큼 이해하기가 까다롭습니다. DFS( ) 메서드를 포함하여 전체 코드를 제공하였습니다. 직접 VS Code에서 돌려보면 동작합니다.

import sys
readl = sys.stdin.readline

def checkSudoku():
    for i in range(3):
        for j in range(9):
            for k in range(1, 10):
                if ch[i][j][k] != 1:
                    return False
    return True

def printSudoku():
    for i in range(9):
        print(*sudoku[i])


def DFS(level, idx):
    if level == zero_cnt:
        if checkSudoku():
            printSudoku()
            exit(0)
        return

    for i in range(1, 10):
        # zeros 리스트에는 (i,j) 형태로 좌표값들을 데이터셋으로 묶여서 입력하였었습니다.
        # zeros 리스트에서 데이터셋을 하나씩 꺼내서 좌표를 (ni,nj) 를 확보합니다.
        ni, nj = zeros[idx]

        # 이 좌표 세트 (ni, nj) 는 체크 매트릭스에 입력해서 
        # 이미 점유가 된 것인지 아직 비어있어서 해당 좌표값이 0인지 점검합니다.
        # 값이 0인 경우에만 이후의 알고리즘을 적용하여 재귀함수를 호출하여 깊이 우선으로 탐색해야 합니다.
        if ch[0][ni][i] != 0 or ch[1][nj][i] != 0 or ch[2][3 * (ni // 3) + nj // 3][i] != 0:
            continue

        # (ni,nj) 좌표값을 지금부터 사용할 것이므로 
        # 각 체크 매트릭스에 0차원 배열에도 1을 값으로 입력해주고 
        # 1차원 매트릭스와 2차원 매트릭스에도 각각 1을 설정해주어서 다음번에
        # 이 (ni, nj) 좌표가 이미 사용되었던 좌표인지 아닌지 구분해서 사용할 수 있습니다.
        # sudoku[ni][nj] = i 로 입력하여 i 번째 숫자가 입력되었음을 sudoku 매트릭스에 업데이트합니다.

        ch[0][ni][i] = 1
        ch[1][nj][i] = 1
        ch[2][3 * (ni // 3) + nj // 3][i] = 1
        sudoku[ni][nj] = i

        # 재귀 호출로서 (level + 1, idx +1) 로 변경된 데이터셋을 입력해줍니다.

        DFS(level + 1, idx + 1)


        # 체크매트릭스에 각 (ni,nj)가 점유된 적이 없는 것처럼 0으로 설정해줍니다.
        # sudoku[ni][nj] 값도 0으로 설정해주어서 DFS(level+1, idx+1) 을 호출하였을 때에도
        # 맨 윗줄의 if 문에서 각각의 값이 0으로 점검할 때 if 문에 걸리지 않고 아래의 코드가 실행될 수 있도록 합니다.
        # 매우 테크니컬한 코딩방식인데 메모리 사용시간을 줄이고 전체 코드 실행 시간을 줄이기 위한 테크닉입니다.
        ch[0][ni][i] = 0
        ch[1][nj][i] = 0
        ch[2][3 * (ni // 3) + nj // 3][i] = 0
        sudoku[ni][nj] = 0




sudoku = [list(map(int, readl().split())) for _ in range(9)]


ch = [[[0] * 10 for _ in range (9)] for _ in range(3)]

zero_cnt = 0
zeros = []
for i in range(9):
    for j in range(9):
        if sudoku[i][j] == 0:
            zero_cnt += 1
            zeros.append((i, j))
        else:
            ch[0][i][sudoku[i][j]] = 1
            ch[1][j][sudoku[i][j]] = 1
            ch[2][3 * (i // 3) + j // 3][sudoku[i][j]] = 1

DFS(0, 0)

마무리

각 함수 별로 F9 를 눌러서 브레이크 포인트를 걸어서 각 값들을 확인해보고 어떻게 값이 변화하는지 Watch Variable 메뉴를 보면서 확인해 보는 것이 코딩 실력 향상에 도움이 됩니다.

함께 보면 코딩 테스트 준비에 도움 되는 글

네카라쿠배 코딩 테스트를 준비하는 분들께 자주 출제되는 bfs 알고리즘 문제의 풀이 방법을 소개 드립니다. 초보자도 알기 쉽도록 매우 상세하고 쉽게 설명하였으니 꼭 한번 읽어보시고 연습을 많이 해보시기 바랍니다.

백준 3190 뱀 문제 풀이 자세히 보러가기

코딩테스트 백준 5917 PYTHON 풀이 방법 보러가기