백준 2580: 스도쿠

Song-Minhyung·2022년 6월 4일

목록 보기

7/50

문제

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

간단하게 스도쿠의 빈칸을 채우는 문제이다.

입력:
0 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
0 6 0 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7
8 0 4 9 1 3 5 0 6
5 9 6 8 2 0 4 1 3
9 1 7 6 5 2 0 8 0
6 0 3 7 0 1 9 5 2
2 5 8 3 9 4 7 6 0

출력:
1 3 5 4 6 9 2 7 8
7 8 2 1 3 5 6 4 9
4 6 9 2 7 8 1 3 5
3 2 1 5 4 6 8 9 7
8 7 4 9 1 3 5 2 6
5 9 6 8 2 7 4 1 3
9 1 7 6 5 2 3 8 4
6 4 3 7 8 1 9 5 2
2 5 8 3 9 4 7 6 1

Try1

풀이방법1

변수 초기화 부분이다.

const board = Array.from({length: 9}, () => input());
let cnt=0;
let returnFlag = false;

가로줄에서 입력 가능한것을 찾는 함수

const getNumsHorizontal = (y: number) => {
    const inNum: number[] = [];
    for (let i=0; i<9; i++) {
        if ( !board[y].includes(i)){
            inNum.push(i);
        }
    }
    return inNum;
}

세로줄에서 입력 가능한것을 찾는 함수

const getNumsVertical = (x: number) => {
    const inNum: number[] = [];
    const verticalBoard = Array.from({length: 9}, (_,i) => board[i][x]);
    for (let i=0; i<9; i++) {
        if ( !verticalBoard.includes(i)){
            inNum.push(i);
        }
    }
    return inNum;
}

3x3 사각형 안에서 입력 가능한것을 찾는 함수

const getNumsSquare = (startX: number, startY: number) =>{
    const inNum: number[] = [];
    const squareBoard: number[] = [];

    for (let y=startY; y<startY+3; y++) {
        for (let x=startX; x<startX+3; x++) {
            squareBoard.push(board[y][x]);
        }
    }
    for (let i=0; i<9; i++) {
        if (!squareBoard.includes(i)) {
            inNum.push(i);
        }
    }
    return inNum;
}

위의 세개의 함수를 사용해서 해당 칸 하나에서 입력 가능한 값들을 반환하는 함수

const getNeedNum = (y:number, x: number) => {
    if (board[y][x] !== 0){
        return [];
    }

    const startX = Math.floor(x/3) * 3; // 0 ~ 2;
    const startY = Math.floor(y/3) * 3; // 0 ~ 2;

    const needNumVertical = getNumsVertical(x);
    const needNumHorizontal = getNumsHorizontal(y);
    const needSquare = getNumsSquare(startX, startY);

    const needNum= [...needNumVertical, ...needNumHorizontal, ...needSquare];
    const needNumCnt = {...Array(9).fill(0)};
    needNum.forEach( v => {
        // console.log(v);
        needNumCnt[v] ++;
    })
    const objArr = Object.entries(needNumCnt);
    return objArr.filter( v => v[1] === 3).map( v => +v[0]);

}

DFS로 배열을 탐색하는 함수

const find = (nowX: number, nowY: number) => {
    if (nowX === 9){
        nowX = 0;
        nowY += 1;
    }
    if (nowY === 9 || returnFlag){
        returnFlag = true;
        return;
    }

    for (let i= nowX; i<9; i++) {
        const possibleNumbers = getNeedNum(nowY, nowX);
        possibleNumbers.forEach( pNum => {
            board[nowY][nowX] = pNum;
            find( i+1, nowY)
        });
        if (board[nowY][nowX] === 0) {
            // 해당 칸에 들어갈 수 있는 숫자
            const possibleNumbers = getNeedNum(nowY, nowX);
            
        }
        find(i+1, nowY);
        if (returnFlag){
            return;
        }
        
    }
}

find(0,0);
board.forEach( row =>{
    console.log(row.join(" "));
});

역시나도 이번에도 깔끔하게 틀림으로 시작했다.

Catch1

문제는 여러개가 있었다.

예시 입력은 잘 되지만 81개가 전부 0이라면 문제가 생김(논리오류)
너무 많은 for문으로 인한 속도초과

Finally1

두가지 문제는 모두 알고리즘을 처음부터 생각하면 될것같다.

Try2

풀이방법2

첫번째 시도한 방법은 그냥 생각없이 대충짜서 그런지
생각보다 이상하게 작동하는 부분이 많았다. 그래서 새로 갈아엎어버렸다.

const board = Array.from({length: 9}, () => input());
let cnt=0;
let returnFlag = false;

const getNumsHorizontal = (y: number) => {
    const inNum: number[] = [];
    for (let i=1; i<10; i++) {
        if ( !board[y].includes(i)){
            inNum.push(i);
        }
    }
    return inNum;
}

const getNumsVertical = (x: number) => {
    const inNum: number[] = [];
    const verticalBoard = Array.from({length: 9}, (_,i) => board[i][x]);
    for (let i=1; i<10; i++) {
        if ( !verticalBoard.includes(i)){
            inNum.push(i);
        }
    }
    return inNum;
}

const getNumsSquare = (startX: number, startY: number) =>{
    const inNum: number[] = [];
    const squareBoard: number[] = [];

    for (let y=startY; y<startY+3; y++) {
        for (let x=startX; x<startX+3; x++) {
            squareBoard.push(board[y][x]);
        }
    }
    for (let i=1; i<10; i++) {
        if (!squareBoard.includes(i)) {
            inNum.push(i);
        }
    }
    return inNum;
}

const getNeedNum = (y:number, x: number) => {
    if (board[y][x] !== 0){
        return [];
    }

    const startX = Math.floor(x/3) * 3; // 0 ~ 2;
    const startY = Math.floor(y/3) * 3; // 0 ~ 2;

    const needNumVertical = getNumsVertical(x);
    const needNumHorizontal = getNumsHorizontal(y);
    const needSquare = getNumsSquare(startX, startY);

    const needNum= [...needNumVertical, ...needNumHorizontal, ...needSquare];
    const needNumCnt = {...Array(10).fill(0)};
    needNum.forEach( v => {
        // console.log(v);
        needNumCnt[v] ++;
    })
    const objArr = Object.entries(needNumCnt);
    return objArr.filter( v => v[1] === 3).map( v => +v[0]);

}

const find = (y: number, x: number) => {
    if (x === 9){
        x = 0;
        y += 1;
    }
    if (y === 9 || returnFlag){
        returnFlag = true;
        return;
    }

    const numBeforeChange = board[y][x]; 
    const possibleNumbers = getNeedNum(y, x);

    if (possibleNumbers.length === 0 && board[y][x] !== 0){
        find(y, x+1);
    }
    possibleNumbers.forEach( num => {
        if (returnFlag) return;
        board[y][x] = num;
        find(y, x+1);
        if (returnFlag) return;
        board[y][x] = numBeforeChange;
    });
    // }
}

find(0,0);
board.forEach( v =>{
    console.log(v.join(" "));
});

이번에는 논리적으로 오류가 나는부분을 완벽하게 고쳤다.
이전에는 재귀함수를 부른 후에 값이 제대로 복구가 되질 않았는데
재귀함수 분기를 제대로 나눠줘서 해당 문제는 해결되었다.

Catch2

이번에는 거의다 채점이 되고나서 시간초과가 나왔다.
오류가 나는부분은 제대로 고쳤다고 생각하니 그래도 뿌듯했다.

문제가 되는 부분은 getNumsHorizontal, getNumsVertical, getNumsSquare, getNeedNum 함수로 보인다. 여기서 for문을 어마무시하게 돌려버린다.

Finally2

중복되는 부분을 합기만해도 시간초과 문제는 해결될걸로 보인다.

Try3

풀이방법

const board   = Array.from({length: 9}, () => input());
let returnFlag = false;

const getNeedNum = (y:number, x: number) => {
    if (board[y][x] !== 0){
        return [];
    }

    const startX = Math.floor(x/3) * 3; // 0 ~ 2;
    const startY = Math.floor(y/3) * 3; // 0 ~ 2;
    const squareBoard: number[] = [];
    const board_h: number[] = Array.from({length: 9}, (_,i) => board[i][x]);
    const result: number[] = [];

    // square board init
    for (let y = startY; y < startY + 3; y++) {
        for (let x = startX; x < startX + 3; x++) {
            squareBoard.push(board[y][x]);
        }
    }
    
    for (let i=1; i<10; i++) {
        if ( !board[y].includes(i)
        && !board_h.includes(i)
        && !squareBoard.includes(i)
        ){
            result.push(i);
        }
    }
    return result;
}

const find = (y: number, x: number) => {
    if (x === 9){
        x = 0;
        y += 1;
    }
    if (returnFlag || y === 9 ){
        returnFlag = true;
        return;
    }


    if (board[y][x] === 0){
        const possibleNumbers = getNeedNum(y, x);
        const numBeforeChange = board[y][x]; 

        possibleNumbers.forEach( num => {
            if (returnFlag) return;
            board[y][x] = num;
            find(y, x+1);
            if (returnFlag) return;
            board[y][x] = numBeforeChange;
        });
    }else {
        find(y, x+1);
    }
}

find(0,0);
board.forEach( v =>{
    console.log(v.join(" "));
});

getNumsHorizontal, getNumsVertical, getNumsSquare, getNeedNum 를
getNeedNum 하나로 합치기만 했는데 문제는 성공했다.!!!!!!
하지만 걸린 시간이 4376.... 이 문제는 차후에 해결해보도록 하곘다