소프티어

테스트 케이스 39, 40 시간 초과

두번 다시는 안봤으면 하는 문제에요

const fs = require('fs');
const input = fs.readFileSync('input.txt', 'utf8').trim().split(/\n+/);
const N = Number(input[0].trim())

const problems = Array.from({length: N}, () => [])
for (let i = N * 3; i > 0; i--) {
    input[i].split(' ').forEach((v, i) => {
        problems[i].push(v)
    })
}

function iHateThisProblem() {
    // 격자 생성에 사용. 이것은 dfs 함수 내에 존재하는 또 다른 currentRemoveIndexList로 추가되고 삭제될 예정
    // 이건 problems 기준. 입력 배열 기준
    const totalRemoveIndexList = Array.from({length: N}, () => new Set())
    // time, 시간대에 대한 전체 삭제 목록. 방문 기록 역할
    // 이건 격자 기준 기록
    const removeIndexListByTime = [
        Array.from({length: N}, () => new Set()),
        Array.from({length: N}, () => new Set()),
        Array.from({length: N}, () => new Set())
    ]
    // 시간대 격자. 3초
    const gridByTime = [
        Array.from({length: N}, () => []),
        Array.from({length: N}, () => []),
        Array.from({length: N}, () => []),
    ]
    // 현재 시간
    let currentTime = 0

    // totalRemoveIndexList 을 사용해서 이전 시간대 기준 격자 생성
    function createGrid() {
        for (let i = 0; i < N; i++) {
            let h = 0
            for (let j = 0; j < N * 3; j++) {
                // 제거 목록에 index가 들어가 있지 않으면
                if (!totalRemoveIndexList[i].has(j)) {
                    gridByTime[currentTime][i][h] = j
                    h++
                }

                if (h >= N) {
                    break
                }
            }
        }
    }

    // 격자 좌표로 원본 배열을 참조하여 색 값 얻기
    function getColor(w, h) {
        const index = gridByTime[currentTime][w][h]
        return problems[w][index]
    }

    // 컬러 확인 제거. removeIndexListByTime 요소만 수정됨
    function simulate(w, h) {
        const removeStack = []

        removeIndexListByTime[currentTime][w].add(h)
        const bfsStack = [[w, h]]

        let score = 0
        let top = Number.MIN_SAFE_INTEGER
        let bottom = Number.MAX_SAFE_INTEGER
        let left = Number.MAX_SAFE_INTEGER
        let right = Number.MIN_SAFE_INTEGER

        const basicColor = getColor(w, h)


        while (bfsStack.length > 0) {
            const [cw, ch] = bfsStack.pop()
            // 제거한 위치 problems 기준 기록
            removeStack.push([cw, gridByTime[currentTime][cw][ch]])

            score++
            if (top < ch) top = ch
            if (bottom > ch) bottom = ch
            if (right < cw) right = cw
            if (left > cw) left = cw

            // ch + 1 이 존재하고 && 격자의 해당 위치가 가진 index가 제거된 것이 아니라면 && 색이 같으면
            if (gridByTime[currentTime][cw][ch + 1] !== undefined &&
                !removeIndexListByTime[currentTime][cw].has(ch + 1) &&
                getColor(cw, ch + 1) === basicColor
            ) {
                // 제거 목록에 추가
                removeIndexListByTime[currentTime][cw].add(ch + 1)
                // 스택 추가
                bfsStack.push([cw, ch + 1])
            }
            // ch - 1 이 존재하고 && 격자의 해당 위치가 가진 index가 제거된 것이 아니라면
            if (gridByTime[currentTime][cw][ch - 1] !== undefined &&
                !removeIndexListByTime[currentTime][cw].has(ch - 1) &&
                getColor(cw, ch - 1) === basicColor
            ) {
                // 제거 목록에 추가
                removeIndexListByTime[currentTime][cw].add(ch - 1)
                // 스택 추가
                bfsStack.push([cw, ch - 1])
            }
            // cw + 1 이 존재하고 && 격자의 해당 위치가 가진 index가 제거된 것이 아니라면
            if (gridByTime[currentTime][cw + 1] !== undefined &&
                !removeIndexListByTime[currentTime][cw + 1].has(ch) &&
                getColor(cw + 1, ch) === basicColor
            ) {
                // 제거 목록에 추가
                removeIndexListByTime[currentTime][cw + 1].add(ch)
                // 스택 추가
                bfsStack.push([cw + 1, ch])
            }
            // cw - 1 이 존재하고 && 격자의 해당 위치가 가진 index가 제거된 것이 아니라면
            if (gridByTime[currentTime][cw - 1] !== undefined &&
                !removeIndexListByTime[currentTime][cw - 1].has(ch) &&
                getColor(cw - 1, ch) === basicColor
            ) {
                // 제거 목록에 추가
                removeIndexListByTime[currentTime][cw - 1].add(ch)
                // 스택 추가
                bfsStack.push([cw - 1, ch])
            }
        }
        // 점수 계산
        score += (top - bottom + 1) * (right - left + 1)

        // 제거 한 것들 index 반환. 점수도
        return [removeStack, score]
    }


    let maxScore = 0
    let totalScore = 0
    function dfs() {
        createGrid()
        //console.log(currentTime, totalScore)


        for (let i = 0; i < N; i++) {
            for (let j = 0; j < N; j++) {
                // 시간대 && 격자 기준으로 제거 된 영역인지
                if (!removeIndexListByTime[currentTime][i].has(j)) {
                    const [removeStack, score] = simulate(i, j)

                    currentTime++
                    // 3초가 다 지났으면
                    if (currentTime === 3) {
                        if (maxScore < totalScore + score) {
                            maxScore = totalScore + score
                        }
                        currentTime--
                        continue
                    }

                    // 제거 기록
                    // [[cw, i], ...]
                    removeStack.forEach(array => {
                        const [cw, i] = array
                        totalRemoveIndexList[cw].add(i)
                    })
                    totalScore += score
                    // 제거기록 가지고 다음 단계
                    dfs()
                    // 이번 단계에서 제거한거 복구
                    removeStack.forEach(array => {
                        const [cw, i] = array
                        totalRemoveIndexList[cw].delete(i)
                    })
                    totalScore -= score
                    currentTime--

                }
            }
        }

        // 시간대 격차 방문 초기화 clear
        removeIndexListByTime[currentTime].forEach((v, i) => {
            removeIndexListByTime[currentTime][i] = new Set()
        })
    }
    dfs()

    return maxScore
}

const t= iHateThisProblem()
console.log(t)