※개인 공부 목적의 정리글입니다.
이 글의 내용이 최선의 해답은 아닐 수 있습니다.
문제
스도쿠는 18세기 스위스 수학자가 만든 ‘라틴 사각형’이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.
나머지 빈 칸을 채우는 방식은 다음과 같다.
- 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
- 굵은 선으로 구분되어 있는 3×3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.
또한 위쪽 가운데 위치한 3×3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.
이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.
게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.
입력
아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.
출력
모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.
스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.
제한
- 12095번 문제에 있는 소스로 풀 수 있는 입력만 주어진다.
- C++14: 80ms
- Java: 292ms
- PyPy3: 1172ms
설명
간단하다. 그냥 입력으로 주어지는 스도쿠를 풀어서 출력한다. 풀 수 있는 방법이 여러 개이면 그 중 아무거나 하나를 출력한다.
풀이
제한 부분을 보면 뭔가 있긴 한데 딱히 신경 안써도 되는 부분같다. 스도쿠의 규칙은 문제에 적혀있으니 생략한다.
입력으로 주어지는 스도쿠 판을 2차원 int 배열에 집어넣는다. 그러면서 0인 칸(빈 칸)의 개수를 센다.
빈칸의 개수만큼 blanks 배열을 만든다. 이 배열은 2차원 배열로, 빈 칸의 좌표를 저장할 것이다. 각 행은 길이가 2인 int 배열을 가지고, 순서대로 빈 칸의 y, x좌표를 저장할 것이다.
이후 메소드를 호출하며 첫 번째 빈칸부터 시작한다.
코드
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
sb = new StringBuilder();
int zerocnt = 0; // 빈칸의 개수를 셀 변수
// 이차원 int 배열 map에 입력된 스도쿠 판을 넣는다
for(int i=0; i<9; i++){
String[] row = br.readLine().split(" ");
for(int j=0; j<9; j++){
map[i][j] = Integer.parseInt(row[j]);
if(map[i][j] == 0){
zerocnt++; // 빈 칸이 있으면 빈 칸 개수++
}
}
}
blanks = new int[zerocnt][2]; // 빈칸의 좌표 저장용
int pos = 0;
// map을 순회하며 0인 칸을 찾아 좌표 저장
for(int i=0; i<9; i++){
for(int j=0; j<9; j++){
if(map[i][j] == 0){
blanks[pos][0] = i;
blanks[pos][1] = j;
pos++;
}
}
}
sudoku(0); // 0번 빈칸부터 시작
br.close();
}풀기 전에 입력을 받고 빈칸 좌표를 저장한다.
public static void sudoku(int i){
if(i == blanks.length){ // 마지막 빈칸까지 찾았으면
// 다 채워진 map을 출력
for(int ii=0; ii<9; ii++){
for(int j=0; j<9; j++){
sb.append(map[ii][j]).append(" ");
}
sb.append("\n");
}
System.out.println(sb.toString());
System.exit(0); // 만들 수 있는 한 경우만 출력하면 되므로 한 판 출력후 프로그램 종료
}
// 현재 빈칸의 좌표
int y = blanks[i][0];
int x = blanks[i][1];
for(int n=1; n<=9; n++){ // 이 빈칸에 1부터 9까지 다 넣어보기 위한 루프
if(possible(x, y, n)){ // 현재 빈칸 좌표에 n이 들어갈 수 있나 체크
map[y][x] = n; // 가능하면 실제로 n을 넣고
sudoku(i+1); // 다음 빈칸 찾기
}
}
// 1부터 9까지 넣을 수 있는게 없으면 해당 칸은 다시 비우고 이전 호출로 가서 다시 숫자 조정
map[y][x] = 0;
}public static boolean possible(int x, int y, int n){
for(int yy=0; yy<9; yy++){
if(yy != y && map[yy][x] == n) return false; // 현재 행 제외, 해당 숫자의 위아래에 동일 숫자 있는지
if(yy == y){ // 해당 숫자가 있는 행에서
for(int xx=0; xx<9; xx++){ // 현재칸 제외, 좌우로 같은 숫자가 있는지
if(xx != x && map[y][xx] == n) return false;
}
}
}
int block_y = (int)(y/3)*3; // 블록은 3x3 단위이므로 현재 좌표를 3으로 나눈 몫에 3을 곱하여 블록의 시작 좌표 구함
int block_x = (int)(x/3)*3;
// 블럭단위로 겹침 확인
for(int yy=block_y; yy<block_y+3; yy++){
for(int xx=block_x; xx<block_x+3; xx++){ // 블록 안을 탐색
if(xx != x && yy != y && map[yy][xx] == n) return false; // 현재 탐색중인 칸이 현재 빈 칸이 아닌데 n이 있다면 중복이므로 불가
}
}
// 위 조건을 모두 통과하면 가능
return true;
}블록의 좌표를 구하는 원리는 이렇다. 한 블록은 3×3크기이며, 스도쿠 판은 왼쪽 상단을 기준으로 0부터 시작하는 인덱스를 가진다. 어떤 칸이 몇 번째 블록에 속하는지 구하는 것인데, 만약 어떤 칸의 x좌표가 5라면 왼쪽에서 두 번째 블록에 블록, 즉 중간에 위치한 블록에 속할 것이다.
위 그림을 보면 블록의 좌표 범위는 0~2, 3~5, 6~8이다. 색칠 된 칸의 경우 x좌표는 5이며 \(5 \div 3=1.666…\)으로 몫인 1에다가 블록의 가로 길이인 3을 곱한 3이 곧 이 칸이 속한 블록의 시작 x좌표이다.
시작 y좌표도 마찬가지로 구할 수 있다. 위 그림에서 색칠한 칸의 y좌표는 2이며, \(2 \div 3=0.666…\)으로 몫인 0에 3을 곱한 0이 시작 y좌표가 되겠다.
특정 칸의 위 아래 옆 밑 블록 안을 검사할 때 당연히 특정 칸 자신의 좌표일 때는 검사하지 않아야 한다. 특정 칸 이외의 칸에서 겹치는 숫자가 있는지 확인하는 것이기 때문이다.
이번 문제는 스도쿠의 조건에 맞추어 검사하는 부분만 잘 만들고, 경우의 수가 여러개 이더라도 한 경우만 출력하고 프로그램을 종료시켜주기만 하였다면 크게 어려운 부분은 없는 문제였다.
댓글