스도쿠(2580)
조금 더 복잡한 백트래킹 문제 2
문제
스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.
나머지 빈 칸을 채우는 방식은 다음과 같다.
각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.
또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.
이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.
게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.
입력
아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.
출력
모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.
스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.
제한
baekjoon의 백트래킹 알고리즘으로 풀 수 있는 입력만 주어진다. 다음은 그 알고리즘의 수행 시간이다.
C++14: 80ms
Java: 292ms
PyPy3: 1172ms
예제 입력
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에러가 뜨고 있는데 왜지..? 설마 벡터하나썼다고??
답뒤져보니까 ArrayList를 많이쓰던데
-> 이문제는 아니고
아니면 반례가 있는건가
-> 다 0을 넣고 돌리면 무한으로 계속 나옴 이거 해결해봐야할듯
이게 print하는 부분에서 마지막에 그냥 return해줬는데 이렇게하니까 무한으로 돌아가는 그런 현상이 일어난거같다...
만약에 끝내야하는 상황이 온다면 그때는 return을 사용하지 말고 System.exit(0) 을 사용해서 그냥 프로그램을 종료시키자 실제로 이렇게 바꾸니까 맞음...
풀이
import java.io.*;
import java.util.*;
public class Main{
static int arr[][] = new int[9][9];
//빈 자리의 포인트를 벡터로 저장
static ArrayList<Point> al = new ArrayList<>();
// static Vector<Point> v = new Vector<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
for (int i = 0; i < 9; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < 9; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
//여기서 입력받은 숫자가 0이면 벡터에 저장해둔다.
if(arr[i][j] == 0)
al.add(new Point(i, j));
}
}
dfs(0);
}
public static void dfs(int depth){
if(depth==al.size()){
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
System.exit(0);;
}
int x = al.get(depth).x;
int y = al.get(depth).y;
for (int i = 1; i <= 9; i++) {
if(check(x,y,i)){
arr[x][y] = i;
dfs(depth+1);
arr[x][y] = 0;
}
}
}
public static boolean check(int x, int y, int num){
//0일때 진행해야하기 때문에,
if(arr[x][y] == 0) {
for (int i = 0; i < 9; i++) {
//가로, 세로에 num이 존재하는지 확인,
if(arr[i][y] == num || arr[x][i] == num)
return false;
}
//현재 좌표가 3x3 기준으로 어디 박스에 있는지를 체크하고 그 박스의 시작점으로 위치하시키기 위한 변수,
int sx = x/3*3;
int sy = y/3*3;
//박스를 돌면서 3개씩 위아래로 num이 존재하는지 확인,
for (int i = sx; i < sx+3; i++) {
for (int j = sy; j < sy+3; j++) {
if(arr[i][j] == num)
return false;
}
}
}
return true;
}
public static class Point{
private int x,y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
}
}2번째 시도
import java.io.*;
import java.util.*;
public class Main {
static int[][] arr;
static boolean[][] visited;
static ArrayList<int[]> list;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
arr = new int[9][9];
visited = new boolean[9][9];
list = new ArrayList<>();
for (int i = 0; i < 9; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < 9; j++) {
int recv = Integer.parseInt(st.nextToken());
arr[i][j] = recv;
//위는 값을 입력받아서 배열에 집어넣어주는 과정인데
//입력받을 때 0(빈칸)을 체크해둬야 0을 기준으로 값을 넣을 수 있는지 검증할 수 있다.
if (recv == 0)
list.add(new int[]{i, j});
}
}
dfs(0);
}
//dfs를 구현한 함수
public static void dfs(int cnt) {
//여기서도 살짝 헤멨는데 깊이를 의미하는 cnt를 돌리게되는데 이걸 0의 갯수를 기록해둔 arraylist를 기준으로 잡으면 됬다.
if (cnt == list.size()) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
//스도쿠의 답이 여러개일 수 있는 경우가 있기 때문에
//단 하나의 답을 출력해주기 위해서 답이 나오게 되면 출력하고 코드 종료
System.exit(0);
}
//검사하는 함수를 만들긴했지만 문제가 있었던건 0을 체크해서 기록해둬야하는데 어떻게 기록해야하나였다.
//여기부분은 뭔가 알것 같으면서도 헷갈려서 찾아봤는데 기존에는 vector를 사용해서 구현했었고, arraylist가 적절했다.
//그래서 x,y값을 순서대로 가지고 있는 1차원 배열을 생성해서 순서대로 넣고 그 배열들을 가진 arraylist를 만듬
//체크하는 방식은 1~9를 순서대로 넣으면서 값이 들어갈 수 있는지 확인
for (int i = 1; i <= 9; i++) {
//기존에 만든 검사여부를 확인해서 모두 만족시 dfs진행
if (rowCheck(list.get(cnt)[0], list.get(cnt)[1], i) && squareCheck(list.get(cnt)[0], list.get(cnt)[1], i)) {
//성공했다는 의미는 값이 들어갈 수 있다는 의미이기 떄문에 값 넣어주고
arr[list.get(cnt)[0]][list.get(cnt)[1]] = i;
//다음 0자리로 넘어가서 진행
dfs(cnt + 1);
//만약 진행과정에서 문제가 생겨서 함수를 튀어나올 시, 이전에 진행했던 값을 취소해줘야 위에서 다음 것으로 진행한 것을 다시 되돌릴 수 있다.
arr[list.get(cnt)[0]][list.get(cnt)[1]] = 0;
}
}
}
//입력받은 스도쿠판의 좌표에 숫자가 들어갈 수 있는지 체크하는 함수들 -> 좌표와 어떤 값이 들어갈 수 있는지 확인해서 가능/불가능으로 체크
//가로와 세로줄에 숫자가 들어갈 수 있는지 확인하는 함수
public static boolean rowCheck(int x, int y, int num) {
for (int i = 0; i < 9; i++) {
if (arr[i][y] == num || arr[x][i] == num)
return false;
}
return true;
}
//3x3박스에 숫자가 들어갈 수 있는지 확인하는 함수
public static boolean squareCheck(int x, int y, int num){
//어떠한 좌표가 들어왔을 때 어떤 박스에 해당하는지 확인하기 위해서
//모든 좌표를 그리고 숫자를 들여다보니까 이렇게 공식을 적으면 가능하다는 것을 알게됨
int startX = x / 3 * 3;
int startY = y / 3 * 3;
for (int i = startX; i < startX + 3; i++) {
for (int j = startY; j < startY + 3; j++) {
if (arr[i][j] == num)
return false;
}
}
return true;
}
}Last updated
Was this helpful?