BOJ 2239 - 스도쿠

작년 BOJ 단계별 풀이를 진행할 때 백트래킹 단계에서 풀었던 BOJ 2580과 거의 똑같은 문제다.
당시에는 DFS나 재귀를 거의 다뤄보지 않은 상태였어서 N-Queen과 함께 가장 어려워했던 문제였는데, solved.ac의 class3/4에서 탐색 관련 문제를 주구장창 풀었다보니 이번엔 다소 쉽게 접근할 수 있었다.

기본적으로 DFS로 접근하면서, 각 빈 칸에 넣을 수 있는 값이 있다면 다음으로, 그렇지 않다면 멈추는 방식으로 풀이했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
	// 각 셀의 그룹 리스트
    static ArrayList<Group> groupList = new ArrayList<>();
    
    // 스도쿠 배열
    static Cell[][] cells = new Cell[9][9];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// 그룹 생성
        for(int i = 0; i<9; i++){
            groupList.add(new Group(i));
        }

		// 셀과 그룹 매핑
        for( int i = 0 ; i<9; i++){
            String line = br.readLine();
            for(int j = 0; j<9; j++){
                Group group = groupList.get(setGroup(i,j));
                Cell cell = new Cell( line.charAt(j)-'0', group );
                cells[i][j] = cell;
                group.cellList.add(cell);
            }
        }

        dfs(0, 0);
    }


    public static void dfs(int row, int col){
    	// 8열을 넘어가면 행을 바꿔준다
        if(col==9){
            dfs(row+1, 0);
            return;
        }
        
        // 마지막 행이라면 출력 후 종료
        if(row==9){
        	StringBuilder sb = new StringBuilder();
            for(int i = 0 ; i<9; i++){
                for( int j = 0; j<9; j++){
                    sb.append(cells[i][j].value);
                }
                sb.append("\n");
            }
            System.out.println(sb.toString());
            System.exit(0);
        }
		
        // 셀 값 가져오기
        Cell cell = cells[row][col];
        
        // 셀의 값이 이미 채워져있다면 다음 칸으로
        if(cell.value!=0){
            dfs(row, col+1);
            return;
        }
		
        // 빈칸이라면 가능한 값을 넣고 다음 칸으로
        	// 사전 순 정렬을 요구하고 있기 때문에 낮은 값부터 넣어주면 첫번째 완성되는 값이 정답이 된다.
        for(int k = 1; k<=9; k++){
            if(isPossible(k, row, col)){
                cell.value = k;
                dfs(row, col+1);
                cell.value = 0;
            }
        }
    }

    public static boolean isPossible(int value, int row, int col){
        Group group = cells[row][col].group;
        for(int i = 0 ; i<9; i++){
            // 행, 열, 소속 그룹 검사
            if(cells[row][i].value == value || cells[i][col].value == value || group.cellList.get(i).value == value){
                return false;
            }
        }
        return true;
    }

    public static int setGroup(int i, int j){
        int ret;
        if(i<3){
            if(j<3){ ret = 0; }
            else if(j<6){ ret = 1; }
            else{ ret = 2; }
        }else if(i<6){
            if(j<3){ ret = 3; }
            else if(j<6){ ret = 4; }
            else{ ret = 5; }
        }else{
            if(j<3){ ret = 6; }
            else if(j<6){ ret = 7; }
            else{ ret = 8; }
        }
        return ret;
    }
}

class Cell{
    int value;
    Group group;
    Cell(int value, Group group){
        this.value = value;
        this.group = group;
    }
}

class Group{
    int idx;
    ArrayList<Cell> cellList = new ArrayList<>();
    Group(int idx){
        this.idx = idx;
    }
}

solved.ac의 class3을 풀면서 생긴 습관이 하나 있는데, 효율이 다소 떨어질지 몰라도 어떤 칸이 어떤 정보라는 걸 인식하기 쉽도록 class를 먼저 만들고 그 안에 관련된 데이터를 집어넣는 것이다. 메모리에도, 속도에도 하등 도움이 되지 않는 일이지만 아직 내게는 저렇게 하는 게 머릿속의 방법론을 코드로 바꾸는데에는 도움이 더 되는 것 같다.

실제로 속도는 작년에 제출한 코드에 비해 2배로 늘었다...🥲
실행 속도는 느려졌을지언정 풀이 속도가 훨씬... 정말 훠얼씬 빨라졌다는 걸 위안으로 삼으면서, 오랜만의 포스팅은 끝!