[백준] 스도쿠

백준 2580번: 스도쿠

> https://www.acmicpc.net/problem/2580

2580번: 스도쿠

 

⌨ 입력

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

 

💻 출력

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.
스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

 

 

---

☝ 첫번째 풀이

배열을 순회하는 것만으로도 풀 수 있지 않을까? 해서 시도해보았다.

테스트 케이스는 성공하지만 제출 시 바로 실패가 떠버린다.

public class Main {
    public static final int N = 9;
    public static int[][] arr = new int[N][N];
    public static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		
        for(int i=0;i<N;i++) {
            arr[i] = Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }
		
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                if(arr[i][j] == 0) putArr(i, j);
                sb.append(arr[i][j]).append(" ");
            }
            sb.append("\n");
        }
		
        System.out.println(sb);
        bf.close();	
    }
    
    private static void putArr(int x, int y) {
        for(int k=1;k<=N;k++) {
            if(checkRange(x, y, k)) {
                arr[x][y] = k;
                return;
            }
        }
    }
    
    private static boolean checkRange(int x, int y, int value) {
        // 가로세로 체크
        for(int i=0;i<N;i++) {
            if(arr[x][i] == value) return false;
            if(arr[i][y] == value) return false;
        }
		
        // 3*3 영역 체크
        int xRange = x/3*3;
        int yRange = y/3*3;
		
        for(int i=xRange;i<xRange+3;i++) {
            for(int j=yRange;j<yRange+3;j++) {
                if(arr[i][j] == value) return false;
            }
        } 
        return true;
    }
}

 

1. 스도쿠 입력 받기
2. 배열 순회
     -> 0인 경우 넣을 수 있는 값 검사해서 값 넣기
     -> StringBuilder에 값 추가
3. StringBuilder 출력

 

뭔가 제외된 조건이 있나해서 계속 돌려보다가...

결국 오카방에서 도움을 받았다 😥

 

배열 순회로 될 것 같은데 왜 백트래킹 문제인가 했더니...ㅠㅠㅠㅠㅠㅠ

백트래킹 방식으로 코드를 수정해보았다.

 

✌ 두번째 풀이

public class Main {
    public static final int N = 9;
    public static int[][] arr = new int[N][N];
    public static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		
        for(int i=0;i<N;i++) {
            arr[i] = Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }
		
        sudoku(0,0);
        bf.close();	
    }
    
    private static void sudoku(int x, int y) {
        if(y==N) {
            sudoku(x+1, 0); return;
        }
		
        if(x==N) {
            printArr(); System.exit(0);
        }
		
        if(arr[x][y] == 0) {
            for(int k=1;k<=N;k++) {
                if(checkRange(x, y, k)) {
                    arr[x][y] = k;
                    sudoku(x, y+1);
                }
            }
            arr[x][y] = 0;
            return;
        }
        sudoku(x, y+1);
    }
    
    private static void printArr() {
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                sb.append(arr[i][j]).append(" ");
            }
            sb.append("\n");
        } System.out.println(sb);
    }
    
    private static boolean checkRange(int x, int y, int value) {
        // 가로세로 체크
        for(int i=0;i<N;i++) {
            if(arr[x][i] == value) return false;
            if(arr[i][y] == value) return false;
        }
		
        // 3*3 영역 체크
        int xRange = x/3*3;
        int yRange = y/3*3;
		
        for(int i=xRange;i<xRange+3;i++) {
            for(int j=yRange;j<yRange+3;j++) {
                if(arr[i][j] == value) return false;
            }
        } 
        return true;
    }
}

 

테스트케이스에서 주어지지 않는 예외를 생각하는게 정말 중요한 것 같다.

예외처리가 늘 중요한 법인데 자꾸만 문제 지문에만 집착하는 것 같아서 리마인드 겸 간만의 코테 글을 작성해보았다.