[JAVA] 백준 q2580 - 스도쿠

2580번: 스도쿠

---

> 의식의 흐름

한 칸에 대한 주변 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");
        }
    }
}