백준 2580 스도쿠
문제
가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판에서 게임 시작 전 일부 칸에 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈칸을 채우는 방식은 다음과 같다.
1. 각각의 가로 줄과 세로 줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
2. 굵은 선으로 구분되어 있는 3*3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
게임 시작 전 스도쿠 판에 쓰여있는 숫자들의 정보가 주어질 때, 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.
입력
9줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠 판 각 줄에 쓰여 있는 숫자가 한 칸씩 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.
출력
모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.
!! 스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다. !!
예제 입력 1
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
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
풀이
백 트래킹을 이용해서 풀었다.
(0,0)부터 시작해서 한 칸씩 옮겨가며 문제에 주어진 칸 채우기 공식을 만족하는 숫자를 채워 넣고, 이후 다른 칸을 채울 때 규칙에 해당하는 숫자가 없으면 다시 이전에 임의로 채워둔 칸으로 돌아와서 다음 숫자를 넣고 또 다음 칸으로 넘어가는 방법을 모든 칸을 채울 때까지 반복했다.
이 방법으로 문제를 풀고 테스트 케이스도 통과했지만 81칸을 모두 0으로 채운 입력을 넣었을 때 에러가 발생했다. 0 스도쿠는 출력 조건에 나와있는 "방법이 여럿인 경우"에 해당하는 예 중 하나이고, 내가 푼 방식은 방법이 여럿일 경우 계속 출력 하는 방식이기 때문에 오류가 난 것이다. 그렇기 때문에 처음 규칙에 부합하는 결과를 내고 나면 시스템을 종료하는 System.exit(0) 코드를 추가 해 문제를 해결했다.
코드
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int[][] map = new int[9][9]; static StringBuilder sb = new StringBuilder(); // 임의의 칸의 행과 열 인덱스 정보, 해당 칸의 값이 주어지면 // 규칙에 부합하는 지 판단하는 isPossible 함수 // n: 행 인덱스, m: 열 인덱스, val: 해당 칸의 값 static boolean isPossible(int n, int m, int val) { // 가로에 겹치는 값이 있으면 불가능 for(int i=0; i<9; i++) { if(map[n][i]==val) { return false; } } // 세로에 켭치는 값이 있으면 불가능 for(int i=0; i<9; i++) { if(map[i][m]==val) { return false; } } // 네모에 겹치는 값이 있으면 불가능 int nMin = (n/3) * 3; int nMax = nMin +3; int mMin = (m/3) * 3; int mMax = mMin +3; for(int i=nMin; i<nMax; i++) { for(int j=mMin; j<mMax; j++) { if(map[i][j] == val) { return false; } } } return true; } // 백트래킹 static void search(int n, int m) { // 한 행에서 모든 열을 탐색하면 // 다음 행으로 넘어가기 if(m == 9) { search(n+1, 0); return; } // 모든 행의 모든 열을 다 탐색하면 // 정답 출력 후 시스템 종료 if(n==9) { for(int i=0; i<9; i++) { for(int j=0; j<9; j++) { sb.append(map[i][j] + " "); } sb.append("\n"); } System.out.println(sb); System.exit(0); return; } // 해당 칸의 값이 0인 경우(채워져 있지 않은 경우) // 1~9까지의 숫자 중 규칙에 부합하는 값이 있으면 대입, 없으면 이전 칸으로 넘어감 if(map[n][m]==0) { for(int num =1; num<10; num++) { if(isPossible(n, m, num)) { map[n][m] = num; search(n, m+1); } } map[n][m] = 0; return; } search(n, m+1); } public static void main(String[] args) throws IOException, NumberFormatException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = null; for(int i=0; i<9; i++) { st = new StringTokenizer(br.readLine()); for(int j=0; j<9; j++) { map[i][j] = Integer.parseInt(st.nextToken()); } } search(0, 0); } }
