백준 2239번, 2580번 JAVA

하하하핳 백트래킹으로 잘 풀면된다.

예제가 맞는데 틀렸던 이유는 return 조건을 예제에 맞춰서 51일시에 true를 리턴해버려서 발생한

어처구니 없는 실수였다.. 백트래킹을 이제야 제대로 이해한듯 하다.

핵심은 재귀는 결국은 스택인데 만약 조건을 만족시키지 못하면 이전 스택으로 돌아가서 List에 저장된 요소(숫자가 채워져있지 않는 부분)을 다시 체크하면서 다시 스택을 쌓아가고 모두 풀었으면 true를 반환해서 스택을 모두 스킵해버린다.

2239번과 2580번은 단순히 입력과 반환을 어떻게 하느냐의 차이.

import java.io.*;
import java.util.*;

class XY{
    int x;
    int y;

    XY(int x, int y){
        this.x=x;
        this.y=y;
    }
}

public class Main {
    static int[][] maps;
    static ArrayList<XY> checkList = new ArrayList<>();

    public static boolean dfs(int startPoint){
        if(startPoint==checkList.size())
            return true;
        int lowX;
        int lowY;
        int edgeX;
        int edgeY;
        int[] flag = new int[10];
        int x=checkList.get(startPoint).x;
        int y=checkList.get(startPoint).y;
        for(int i=0;i<9;i++){
            if(maps[x][i]!=0){
                flag[maps[x][i]]=1;
            }
        }

        for(int i=0;i<9;i++){
            if(maps[i][y]!=0){
                flag[maps[i][y]]=1;
            }
        }

        if (x >= 0 && x <= 2 && y >= 0 && y <= 2) {
            lowX=0;lowY=0;edgeX=2;edgeY=2;
        } else if (x >= 3 && x <= 5 && y >= 0 && y <= 2) {
            lowX=3;lowY=0;edgeX=5;edgeY=2;
        } else if (x >= 6 && x <= 8 && y >= 0 && y <= 2) {
            lowX=6;lowY=0;edgeX=8;edgeY=2;
        } else if (x >= 0 && x <= 2 && y >= 3 && y <= 5) {
            lowX=0;lowY=3;edgeX=2;edgeY=5;
        } else if (x >= 3 && x <= 5 && y >= 3 && y <= 5) {
            lowX=3;lowY=3;edgeX=5;edgeY=5;
        } else if (x >= 6 && x <= 8 && y >= 3 && y <= 5) {
            lowX=6;lowY=3;edgeX=8;edgeY=5;
        } else if (x >= 0 && x <= 2 && y >= 6 && y <= 8) {
            lowX=0;lowY=6;edgeX=2;edgeY=8;
        } else if (x >= 3 && x <= 5 && y >= 6 && y <= 8) {
            lowX=3;lowY=6;edgeX=5;edgeY=8;
        } else{
            lowX=6;lowY=6;edgeX=8;edgeY=8;
        }

        for(int i=lowX;i<=edgeX;i++){
            for(int j=lowY; j<=edgeY;j++){
                if(maps[i][j]!=0){
                    flag[maps[i][j]]=1;
                }
            }
        }

        for(int i=1;i<10;i++){
            if(flag[i]==0){
                maps[x][y]=i;
                boolean bool = dfs(startPoint+1);
                if(bool){
                    return true;
                }
                maps[x][y]=0;
            }
        }
        return false;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        maps = new int[9][9];

        for (int i = 0; i < 9; i++) {
            String temp = br.readLine();
            for (int j = 0; j < 9; j++) {
                maps[i][j] = Character.getNumericValue(temp.charAt(j));
            }
        }
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(maps[i][j]==0){
                    checkList.add(new XY(i,j));
                }
            }
        }
        dfs(0);
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                bw.write(Integer.toString(maps[i][j]));
            }
            bw.newLine();
        }
        bw.flush();
        bw.close();
    }
}