2580번: 스도쿠
스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루
www.acmicpc.net
> 의식의 흐름
한 칸에 대한 주변 8칸에 겹치는 수가 있으면 안되는 것이라고 착각하고 풀었다가 틀렸습니다가 잔뜩,,,
한 칸에 대한 주변 8칸이 아니라 특정 영역의 정사각형 내에 겹치는 수가 있으면 안된다는 것을 깨닫고 로직을 고쳤더니 통과했다
> 풀이
1. map[][] 입력 받는다. 이때, 빈 칸의 위치를 ArrayList에 담아둔다.
2. 백트래킹 활용
Location loc = blanks.get(idx);
for(int i=1;i<=9;i++){
if(checkPossible(loc.x, loc.y, i) && !isFinish){
map[loc.x][loc.y] = i;
sudoku(idx+1);
}
}
map[loc.x][loc.y] = 0;
1) map[loc.x][loc.y]에 해당하는 칸에 정수 i를 대입한다.
2) 정수 i가 해당 위치에 들어갈 수 있는 수인지 checkPossible() 함수를 통해 확인한다.
3) 만약 가능한 수인 경우, 다음 빈칸에 대해 sudoku() 함수를 수행한다.
다음 빈칸에 대한 sudoku() 수행 시, 모든 빈 칸에 대해 완료된 경우, 그 상황에서의 map을 출력하고 함수를 마친다.
4) 정수 i를 1~9로 변경하며, 1)~3)를 반복한다.
5) 해당 반복문이 끝나면 정수 i를 대입하던 칸을 다시 빈칸으로 만들어준다.
> 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
public static int[][] map = new int[9][9];
public static ArrayList<Location> blanks = new ArrayList<>();
public static boolean isFinish = false;
public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static class Location{
int x;
int y;
public Location(int x, int y){
this.x = x;
this.y = y;
}
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
for(int i=0;i<9;i++){
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=0;j<9;j++){
int num = Integer.parseInt(st.nextToken());
map[i][j] = num;
if(num == 0){ // 빈칸 위치 담아두기
blanks.add(new Location(i,j));
}
}
}
sudoku(0);
bw.flush();
br.close();
bw.close();
}
public static void sudoku(int idx) throws Exception{
if(isFinish) {
return;
}
if(idx == blanks.size()){
isFinish = true;
printAns();
return;
}
Location loc = blanks.get(idx);
for(int i=1;i<=9;i++){
if(checkPossible(loc.x, loc.y, i) && !isFinish){
map[loc.x][loc.y] = i;
sudoku(idx+1);
}
}
map[loc.x][loc.y] = 0;
}
public static boolean checkPossible(int x, int y, int num){
for(int i=0;i<9;i++){
if(i!=y && map[x][i]==num) // 가로 확인
return false;
if(i!=x && map[i][y]==num) // 세로 확인
return false;
}
// 정사각형 주변 8칸 확인
int top = (x/3)*3; // 정사각형의 첫 행 번호
int right = (y/3)*3; // 정사각형의 첫 열 번호
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
int nx = top+i;
int ny = right+j;
if(nx==x && ny==y)
continue;
if(map[nx][ny]==num)
return false;
}
}
return true;
}
public static void printAns() throws Exception{
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
bw.write(Integer.toString(map[i][j])+" ");
}
bw.write("\n");
}
}
}
'알고리즘 > 백준' 카테고리의 다른 글
[JAVA] 백준 q7662 - 이중 우선순위 큐 (0) | 2023.09.15 |
---|---|
[JAVA] 백준 q4358 - 생태학 (0) | 2023.09.14 |
[JAVA] 백준 q3055 - 탈출 (0) | 2023.08.08 |
[JAVA] 백준 q11003 - 최솟값 찾기 (0) | 2023.08.08 |
[JAVA] 백준 q17276 - 배열 돌리기 (0) | 2023.06.22 |