import java.io.*;
import java.util.*;
class EmptyPoint {
int x;
int y;
EmptyPoint(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Sudoku {
private static final int N = 9;
private static final int[] dx = {-1, 1, 0, 0};
private static final int[] dy = {0, 0, -1, 1};
static BufferedReader br;
static StringTokenizer st;
static int[][] board;
static ArrayList<EmptyPoint> emptyPoints;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException{
input();
EmptyPoint first = emptyPoints.get(0);
backtracking(first.x, first.y, 0);
}
static void input() throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
emptyPoints = new ArrayList<>();
board = new int[N][N];
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0; j < N; j++) {
board[i][j] = st.nextToken().charAt(0) - '0';
if(board[i][j] == 0) {
emptyPoints.add(new EmptyPoint(i, j));
}
}
}
}
static void backtracking(int x, int y, int cntNum) {
//현재 위치에 넣을 수 있는 값을 찾는다.
boolean[] visited = isPossible(x, y);
if(cntNum == emptyPoints.size()){
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
if(j == N-1) sb.append(board[i][j]);
else sb.append(board[i][j]).append(' ');
}
sb.append('\n');
}
System.out.print(sb);
System.exit(0);
}
//현재 위치에 값을 넣고 다음 0의 위치로 가서 다시 찾는다.
for(int i = 1; i <= N; i++) {
if(!visited[i]) {
board[x][y] = i;
//종료조건
if(cntNum == emptyPoints.size()-1) backtracking(-1, -1, cntNum+1);
backtracking(emptyPoints.get(cntNum+1).x, emptyPoints.get(cntNum+1).y, cntNum+1);
}
}
board[x][y] = 0;
}
static boolean[] isPossible(int x, int y) {
boolean[] visited = new boolean[10];
//가로, 세로 줄에 중복되는 수 탐색
for(int i = 0; i < 4; i++) {
int xx, yy;
for(int j = 1; j < N; j++) {
xx = x + dx[i] * j;
yy = y + dy[i] * j;
if(xx < 0 || yy < 0 || xx >= N || yy >= N) continue;
visited[board[xx][yy]] = true;
}
}
//3x3에 중복되는 수 탐색
int setX = (x / 3) * 3;
int setY = (y / 3) * 3;
for(int i = setX; i < setX+3; i++) {
for(int j = setY; j < setY+3; j++) {
visited[board[i][j]] = true;
}
}
return visited;
}
}
백트래킹을 이용해서 푼 문제이다.
처음에 0이 있는 곳의 좌표를 클래스로 만들어 ArrayList로 저장해서 그곳만 탐색 하도록 하였다. 그럼 시간단축이 될줄 알았건만 채점해보니 다른 분들의 풀이보다 더 오래걸렸다.. 왤까 isPossible() 때문일까? 그리고 boolean 배열을 만들어 배열 전체를 리턴하다 보니 메모리 사용량도 다른 사람들보다 거의 2~3배는 더 나왔다.. 그래도 일단 구현먼저 해놓고 시간복잡도나 공간복잡도를 줄이는게 급선무다. 그리고 구현해놓고 꼭 최적화도 해보기 !!
'Dev > PS' 카테고리의 다른 글
[백준] 1261 알고스팟 java (0) | 2022.04.11 |
---|---|
[백준] 1806 부분합 java (0) | 2022.03.30 |
[백준] 5014 스타트링크 java (0) | 2022.03.25 |
[백준] 3108 로고 java (0) | 2022.03.24 |
[백준] 1759 암호 만들기 java (0) | 2022.03.22 |