이왓슨 작업실

PS 풀이 BOJ 33562 3분

[백준 33562] shapex

티어: 플5

제2회 유틸컵 당시 7솔 배경을 눈앞에 두고 막힌 통곡의 벽 같은 문제를 드디어 풀었다. 풀고 보니 대회 때도 충분히 풀 수 있었을 것 같은데.. 아쉽다.

결합기를 제외한 나머지 기계는 상대적으로 구현이 쉽다. 결합기를 어떻게 만들어야 할까?

대회 당시 코드를 보니 결합기를 실제로 시뮬레이션하려고 매우 길고 복잡한 casework를 했었다.

하지만 경우의 수는 그리 많지 않다. 몇 칸 결합될 수 있는지만 알면 되기 때문이다.

기본 도형을 aa, aa 위에서 아래로 내려가며 결합할 도형을 bb라고 하자.

모든 도형을 실제 높이에 상관없이 빈 줄을 추가해 4줄로 맞춰준다면 구현이 편리해진다.

결합기의 역할은 aa와 bb가 겹치지 않는 선에서 최대한 bb를 내려주는 것이고, 각 경우에 대해 고려해야 하는 모든 것을 적어보자.

i. 1줄을 내리려면 aa의 4층과 bb의 1층이 안 겹치면 된다.

ii. 2줄을 내리려면 i 조건에 추가로 aa의 3층과 bb의 1층이 안 겹쳐야 하고, aa의 4층과 bb의 2층이 안 겹쳐야 한다.

iii. 3줄을 내리려면 ii 조건에 추가로 aa의 2층과 bb의 1층이 안 겹쳐야 하고...

iv. 4줄을 내리려면 iii 조건에 추가로 aa의 1층과 bb의 1층이...

이것만 처리해주면 결합기와 같은 역할을 해줄 수 있다.

JavaScript129 lines
var input = require('fs').readFileSync(0,'utf8').trim().split('\n')
var [n, m] = input[0].split(' ').map(Number)
var r = [...Array(101)].map(e => 0)
var color = ['r', 'g', 'b', 'y', 'p', 'c', 'w', 'u']

function J(i,j,k) { //절단기
    if(r[i] == 0) {
        r[j] = 0
        r[k] = 0
    }else {
        var s = r[i].split(':')
        r[j] = s.map(e => '----' + e.slice(4)).filter(e => e != '--------').join(':')
        r[k] = s.map(e => e.slice(0,4) + '----').filter(e => e != '--------').join(':')
        if(r[j] === '') r[j] = 0
        else if(r[k] === '') r[k] = 0
    }

}

function H(i,j,k) { //회전기
    if(r[i] == 0) r[j] = 0
    else if(k == 1) {
        r[j] = r[i].split(':').map(e => e.slice(-2) + e.slice(0, -2)).join(':')
    }else if(k == 2) {
        r[j] = r[i].split(':').map(e => e.slice(4) + e.slice(0, 4)).join(':')
    }else {
        r[j] = r[i].split(':').map(e => e.slice(2) + e.slice(0, 2)).join(':')
    }
}

function G(i, j, k) { //결합기
    if(r[i] == 0 || r[j] == 0) {
        r[k] = 0
        return
    }
    var a = r[i].split(':')
    a.push('--------')
    a.push('--------')
    a.push('--------')
    a.push('--------')
    var b = r[j].split(':')
    b.push('--------')
    b.push('--------')
    b.push('--------')
    b.push('--------')
    a = a.slice(0,4)
    b = b.slice(0,4)
    var dab = a
    var deep = 0
    /*
    a3과 b0
    a2와 b0, a3과 b1
    a1과 b0, a2와 b1, a3와 b2
    a0와 b0, a1와 b1, a2와 b2, a3와 b3
    */
    if(GG(a[3],b[0])) {
        deep++
        if(GG(a[2],b[0])&&GG(a[3],b[1])) {
            deep++
            if(GG(a[1],b[0])&&GG(a[2],b[1])&&GG(a[3],b[2])) {
                deep++
                if(GG(a[0],b[0])&&GG(a[1],b[1])&&GG(a[2],b[2])&&GG(a[3],b[3]))
                    deep++
            }
        }
    }
    switch(deep) {
        case 1:
            dab[3] = GH(a[3],b[0])
            break
        case 2:
            dab[2] = GH(a[2],b[0])
            dab[3] = GH(a[3],b[1])
            break
        case 3:
            dab[1] = GH(a[1],b[0])
            dab[2] = GH(a[2],b[1])
            dab[3] = GH(a[3],b[2])
            break
        case 4:
            dab[0] = GH(a[0],b[0])
            dab[1] = GH(a[1],b[1])
            dab[2] = GH(a[2],b[2])
            dab[3] = GH(a[3],b[3])
            break
    }
    dab = dab.filter(e=>e!='--------')
    r[k]=dab.join(':')||0
}

function GG(s1,s2) { //층 결합 가능 여부 판단
    for(var i = 0; i < 8; i++) {
        if(s1[i]!='-'&&s2[i]!='-') return false
    }
    return true
}

function GH(s1,s2) { //층 결합
    var C = ''
    for(var i = 0; i < 8; i++) C+=s1[i]!='-'?s1[i]:s2[i]
    return C
}

function S(i,j,k) { //색칠기
    if(r[i] == 0) r[j] = 0
    else r[j] = r[i].replace(new RegExp(color.join('|'), 'g'), k)
}

for(var i = 1; i <= n; i++) r[i] = input[i]
for(var i = n+1; i <= n+m; i++) {
    var q = input[i].split(' ')
    switch (+q[0]) {
        case 1:
            J(+q[1],+q[2],+q[3])
            break
        case 2:
            H(+q[1],+q[2],+q[3])
            break
        case 3:
            G(+q[1],+q[2],+q[3])
            break
        case 4:
            S(+q[1],+q[2],q[3])
            break
    }
}

console.log(r[100]==0?'None':r[100])
//console.log(r.join('\n'))

댓글