백준 2580번 스도쿠

< 백준 2580번 스도쿠 - 마포 코딩박 >

사용한 알고리즘: DFS


 9*9 grid 의 스도쿠의 빈칸을 채우는 문제였습니다.
 DFS 를 통해 빈칸을 채워보아 문제를 해결했습니다,

문제풀이 과정은 다음과 같습니다.
(1)
 기본적으로 (i,j) 칸에 k라는 숫자가 들어가려면, i row 와 j column, 그리고 (i,j) 가 위치한 3*3 사각형( (i/3)*3+(j/3) 번째 사각형 ) 안에 k 가 없어야 합니다.

(1) (코드: 40~51)
 각 grid를 입력받으며 해당 숫자를 배열(arr)에 저장해주었습니다. row, col, square 에 해당 숫자가 있음을 저장해주었습니다. 빈칸이 입력되면 이를 따로 pair형태로 저장해주었습니다.

(2) (코드: 10~15)
 (x,y) 칸에 숫자 num 이 들어갈 수 있는지 확인하는 함수를 만들어 줍니다.

(3) (코드: 16~38)
 빈칸을 순서대로 둘러보며, 각 빈칸에 1~9 중 가능한 숫자를 넣어보는 DFS 를 돌렸습니다.
각 빈칸에 k 숫자를 넣어줄 때 row, col, square 도 업데이트 해주어야합니다.