Softeer [Level 3] [HSAT 2회 정기 코딩 인증평가 기출] Garage game {언어 : JavaScript}

문제 링크

https://softeer.ai/practice/6276

Softeer - 현대자동차그룹 SW인재확보플랫폼

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});
const inputData = [];

rl.on('line', (line) => {
    inputData.push(line.split(" ").map((e) => Number(e)));
}).on('close', () => {
    let answer = 0;
    
    const n = inputData[0][0];
    const height = 3 * n;
    const startSquare = 2 * n;
    const board = Array.from({length: height}, (_, i) => inputData[i + 1]);

    // 같은 색을 찾는 보조 함수
    const dr = [-1, 1, 0, 0];
    const dc = [0, 0, -1, 1];
    const isValid = (nr, nc) => {
        return startSquare <= nr && nr < height && 0 <= nc && nc < n;
    }
    
    // 어딜 지울지 찾는 함수
    const delColors = (copyBoard) => {
        const delArrs = [];
        const visited = Array.from({length: n}, () => Array(n).fill(false));
        for (let sr = startSquare; sr < height; sr++) {
            for (let sc = 0; sc < n; sc++) {
                const srst = sr - startSquare;
                if (copyBoard[sr][sc] === 0 || visited[srst][sc]) {
                    continue;
                }
                const deque = [[sr, sc]];
                const deletes = [[sr, sc]];
                // 시작 지점 색깔
                const currentColor = copyBoard[sr][sc];
                // 시작 지점 방문체크 실수 금지
                visited[srst][sc] = true;

                // bfs 시작
                while (deque.length > 0) {
                    const [r, c] = deque.shift();
                    for (let d = 0; d < 4; d++) {
                        const nr = r + dr[d];
                        const nc = c + dc[d];
                        const nrst = nr - startSquare;
                        if (isValid(nr, nc)) {
                            if (visited[nrst][nc] || copyBoard[nr][nc] !== currentColor) {
                                continue;
                            }
                            visited[nrst][nc] = true;
                            deletes.push([nr, nc]);
                            deque.push([nr, nc]);
                        }
                    }
                }
                delArrs.push(deletes);
            }
        }
        return delArrs;
    }

    // 지우는 부분의 점수
    const fcScore = (arr) => {
        if (arr.length === 1) {
            return 2;
        }
        if (arr.length === 2) {
            return 4;
        }
        const rows = arr.map(([r]) => r);
        const cols = arr.map(([, c]) => c);
        const area = (Math.max(...rows) - Math.min(...rows) + 1) * (Math.max(...cols) - Math.min(...cols) + 1);
        return arr.length + area;
    };

    // 이전 코드를 분석해본 결과 재귀가 3번 돌아가는 것이 시간 초과의 원인이 되었다고 생각한다.
    // 재귀를 2번만 돌아가게 만들고 문제를 풀면 비교적 쉽게 풀릴 것 같다.
    // 1회차 시작 => 삭제할 부분 선택 => 제거 => 정렬 => 재귀
    // 2회차 시작 => 삭제할 부분 선택 => 제거 => 정렬
    // 3회차 시작 => 삭제할 부분 선택 => 계
    const dfs = (cnt, copyBoard, score, curDels) => {      
        for (const arr of curDels) {
            const newScore = fcScore(arr) + score;
            const newBoard = copyBoard.map((row) => row.slice());
            // 정렬을 안해도 되는 열을 찾으면 좋을듯
            const checkNoMovedCols = Array(n).fill(0);
            arr.forEach(([r, c]) => {
                newBoard[r][c] = 0;
                checkNoMovedCols[c] = 1;
            });
            // 재 정렬
            for (let c = 0; c < n; c++) {
                if (checkNoMovedCols[c] === 0) {
                    continue;
                }
                let idx = height - 1;
                for (let r = height-1; r > -1; r--) {
                    if (newBoard[r][c] !== 0) {
                        [newBoard[idx][c], newBoard[r][c]] = [newBoard[r][c], newBoard[idx][c]];
                        idx--;
                    }
                }
            }
            // 재귀
            if (cnt === 1) {
                for (const arr2 of delColors(newBoard)) {
                    const doubleScore = fcScore(arr2) + newScore;
                    if (answer < doubleScore) {
                        answer = doubleScore;
                    }
                }
            } else {
                dfs(cnt+1, newBoard, newScore, delColors(newBoard));
            }
        }
    }

    // 함수 실행
    dfs(0, board, 0, delColors(board));
    console.log(answer);
    process.exit(0);
});

틀린 코드

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});
const inputData = [];

rl.on('line', (line) => {
    inputData.push(line.split(" ").map((e) => Number(e)));
}).on('close', () => {
    let answer = 0;
    
    const n = inputData[0][0];
    const height = 3 * n;
    const startSquare = 2 * n;
    const board = Array.from({length: height}, () => [0, 0]);
    for (let i = 1; i <= height; i++) {
        board[i-1] = inputData[i];
    }
    
    // 같은 색을 찾는 보조 함수
    const dr = [-1, 1, 0, 0];
    const dc = [0, 0, -1, 1];
    const isValid = (nr, nc) => {
        return startSquare <= nr && nr < height && 0 <= nc && nc < n;
    }
    
    // 어딜 지울지 찾는 함수
    const delColors = (copyBoard) => {
        const delArrs = [];
        const visited = Array.from({length: n}, () => Array.from({length: n}, () => false));
        for (let sr = startSquare; sr < height; sr++) {
            for (let sc = 0; sc < n; sc++) {
                if (board[sr][sc] === 0 || visited[sr-startSquare][sc]) {
                    continue;
                }
                const deque = [[sr, sc]];
                const deletes = [[sr, sc]];
                // 시작 지점 색깔
                const currentColor = copyBoard[sr][sc];
                // 시작 지점 방문체크 실수 금지
                visited[sr-startSquare][sc] = true;

                // bfs 시작
                while (deque.length > 0) {
                    const [r, c] = deque.shift();
                    for (let d = 0; d < 4; d++) {
                        const nr = r + dr[d];
                        const nc = c + dc[d];
                        if (isValid(nr, nc)) {
                            if (visited[nr-startSquare][nc] || copyBoard[nr][nc] !== currentColor) {
                                continue;
                            }
                            visited[nr-startSquare][nc] = true;
                            deletes.push([nr, nc]);
                            deque.push([nr, nc]);
                        }
                    }
                }
                delArrs.push(deletes);
            }
        }
        return delArrs;
    }

    // 지우는 부분의 점수
    const fcScore =  (arr) => {
        const [fr, fc] = arr[0];
        let [mxr, mxc, mnr, mnc] = [fr, fc, fr, fc];
        arr.forEach(([r, c]) => {
            mxr = Math.max(mxr, r);
            mxc = Math.max(mxc, c);
            mnr = Math.min(mnr, r);
            mnc = Math.min(mnc, c);
        });
        return arr.length + (mxr - mnr + 1) * (mxc - mnc + 1);
    }

    // 이전 코드를 분석해본 결과 재귀가 3번 돌아가는 것이 시간 초과의 원인이 되었다고 생각한다.
    // 재귀를 2번만 돌아가게 만들고 문제를 풀면 비교적 쉽게 풀릴 것 같다.
    // 1회차 시작 => 삭제할 부분 선택 => 제거 => 정렬 => 재귀
    // 2회차 시작 => 삭제할 부분 선택 => 제거 => 정렬
    // 3회차 시작 => 삭제할 부분 선택 => 계
    const dfs = (cnt, copyBoard, score, curDels) => {
        // cnt가 2일 때랑 아닐 때로 나눈다.
        // 지울 부분을 찾는다.
        // 지울 부분이 없다면 종료
        if (curDels.length === 0) {
            if (answer < score) {
                answer = score;
            }
            return;
        }
        
        for (const arr of curDels) {
            const newScore = arr.length === 1 ? 2 + score : fcScore(arr) + score;
            const newBoard = copyBoard.map((e1) => e1.map((e2) => e2));
            arr.forEach(([r, c]) => {
                newBoard[r][c] = 0;
            });
            // 재 정렬
            for (let c = 0; c < n; c++) {
                let idx = height - 1;
                for (let r = height-1; r > -1; r--) {
                    if (newBoard[r][c] !== 0) {
                        [newBoard[idx][c], newBoard[r][c]] = [newBoard[r][c], newBoard[idx][c]];
                        idx--;
                    }
                }
            }
            // 재귀
            if (cnt === 1) {
                for (const arr2 of delColors(newBoard)) {
                    const doubleScore = arr2.length === 1 ? 2 + newScore : fcScore(arr2) + newScore;
                    if (answer < doubleScore) {
                        answer = doubleScore;
                    }
                }
            } else {
                dfs(cnt+1, newBoard, newScore, delColors(newBoard));
            }
        }
    }

    // 함수 실행
    dfs(0, board, 0, delColors(board));
    console.log(answer);
    process.exit(0);
});

풀이 방법

 

최적화

1. board 간단하게 만들기

const visited = Array.from({length: n}, () => Array.from({length: n}, () => false));

const board = Array.from({length: height}, (_, i) => inputData[i + 1]);

2. visited 배열 간단하게 만들기

const visited = Array.from({length: n}, () => Array.from({length: n}, () => false));

const visited = Array.from({length: n}, () => Array(n).fill(false));

3. 점수 계산하는 함수 최적화

// 지우는 부분의 점수
const fcScore =  (arr) => {
    const [fr, fc] = arr[0];
    let [mxr, mxc, mnr, mnc] = [fr, fc, fr, fc];
    arr.forEach(([r, c]) => {
        mxr = Math.max(mxr, r);
        mxc = Math.max(mxc, c);
        mnr = Math.min(mnr, r);
        mnc = Math.min(mnc, c);
    });
    return arr.length + (mxr - mnr + 1) * (mxc - mnc + 1);
}

// 지우는 부분의 점수
const fcScore = (arr) => {
    if (arr.length === 1) {
        return 2;
    }
    if (arr.length === 2) {
        return 4;
    }
    const rows = arr.map(([r]) => r);
    const cols = arr.map(([, c]) => c);
    const area = (Math.max(...rows) - Math.min(...rows) + 1) * (Math.max(...cols) - Math.min(...cols) + 1);
    return arr.length + area;
};

4. 불필요한 연산 삭제

• 높이가 3*n까지 숫자로 가득 차있으므로 지울 부분이 없는 배열이 존재하지 않는다.

// 지울 부분을 찾는다.
// 지울 부분이 없다면 종료
if (curDels.length === 0) {
    if (answer < score) {
        answer = score;
    }
    return;
}

5. 재정렬 하는 부분에서 정렬하지 않는 열을 제외하고 정렬하여 시간을 단축시킨다.

• 또한 깊은 복사를 하는 부분에서 더 빠른 copyBoard.map((e) => e.slice());를 사용한다.

for (const arr of curDels) {
    const newScore = arr.length === 1 ? 2 + score : fcScore(arr) + score;
    const newBoard = copyBoard.map((e1) => e1.map((e2) => e2));
    arr.forEach(([r, c]) => {
        newBoard[r][c] = 0;
    });
    // 재 정렬
    for (let c = 0; c < n; c++) {
        let idx = height - 1;
        for (let r = height-1; r > -1; r--) {
            if (newBoard[r][c] !== 0) {
                [newBoard[idx][c], newBoard[r][c]] = [newBoard[r][c], newBoard[idx][c]];
                idx--;
            }
        }
    }
}

for (const arr of curDels) {
    const newScore = fcScore(arr) + score;
    const newBoard = copyBoard.map((row) => row.slice());
    // 정렬을 안해도 되는 열을 찾으면 좋을듯
    const checkNoMovedCols = Array(n).fill(0);
    arr.forEach(([r, c]) => {
        newBoard[r][c] = 0;
        checkNoMovedCols[c] = 1;
    });
    // 재 정렬
    for (let c = 0; c < n; c++) {
        if (checkNoMovedCols[c] === 0) {
            continue;
        }
        let idx = height - 1;
        for (let r = height-1; r > -1; r--) {
            if (newBoard[r][c] !== 0) {
                [newBoard[idx][c], newBoard[r][c]] = [newBoard[r][c], newBoard[idx][c]];
                idx--;
            }
        }
    }
}

6. 재귀 시점을 구분한다.

• 첫 번째 시뮬레이션이 진행되면 재정렬이 필요하다.
• 두 번째 시뮬레이션이 진행되면 재정렬이 필요하다.
• 하지만 세 번째 시뮬레이션에서는 점수만 몇 점인지 확인하고
  •  삭제, 재정렬은 생략해도 된다.
  • 따라서 cnt === 1일 때 종료시킨다.

// 재귀
if (cnt === 1) {
    for (const arr2 of delColors(newBoard)) {
        const doubleScore = fcScore(arr2) + newScore;
        if (answer < doubleScore) {
            answer = doubleScore;
        }
    }
} else {
    dfs(cnt+1, newBoard, newScore, delColors(newBoard));
}

느낀점

• 문제를 잘 풀었다고 생각했는데 시간초과의 늪에서 빠져나올 수 없었다.
• 심지어 8개월 전에도 이 문제를 해결하려고 애를 썼지만 쉽지 않았고 여러 코드 수정을 통해서 끝내 풀 수 있었다.
• 여기서 더 최적화가 가능할 수 있지만 너무 시간을 쏟기에는 다른 할 일이 많다.