16985 Maaaaaaaaaze (자바스크립트)

문제

평화롭게 문제를 경작하며 생활하는 BOJ 마을 사람들은 더 이상 2차원 미로에 흥미를 느끼지 않는다. 2차원 미로는 너무나 쉽게 탈출이 가능하기 때문이다. 미로를 이 세상 그 누구보다 사랑하는 준현이는 이런 상황을 매우 안타깝게 여겨 아주 큰 상금을 걸고 BOJ 마을 사람들의 관심을 확 끌 수 있는 3차원 미로 탈출 대회를 개최하기로 했다.

대회의 규칙은 아래와 같다.

• 5×5 크기의 판이 5개 주어진다. 이중 일부 칸은 참가자가 들어갈 수 있고 일부 칸은 참가자가 들어갈 수 없다. 그림에서 하얀 칸은 참가자가 들어갈 수 있는 칸을, 검은 칸은 참가자가 들어갈 수 없는 칸을 의미한다.

• 참가자는 현재 위치한 칸에서 면으로 인접한 칸이 참가자가 들어갈 수 있는 칸인 경우 그 칸으로 이동할 수 있다.
• 참가자 중에서 본인이 설계한 미로를 가장 적은 이동 횟수로 탈출한 사람이 우승한다. 만약 미로의 입구 혹은 출구가 막혀있거나, 입구에서 출구에 도달할 수 있는 방법이 존재하지 않을 경우에는 탈출이 불가능한 것으로 간주한다.

이 대회에서 우승하기 위해서는 미로를 잘 빠져나올 수 있기 위한 담력 증진과 체력 훈련, 그리고 적절한 운이 제일 중요하지만, 가장 적은 이동 횟수로 출구에 도달할 수 있게끔 미로를 만드는 능력 또한 없어서는 안 된다. 주어진 판에서 가장 적은 이동 횟수로 출구에 도달할 수 있게끔 미로를 만들었을 때 몇 번 이동을 해야하는지 구해보자. 

입력

첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 의미한다.

출력

첫째 줄에 주어진 판으로 설계된 미로를 탈출하는 가장 적은 이동 횟수를 출력한다. 단, 어떻게 설계하더라도 탈출이 불가능할 경우에는 -1을 출력한다.

======

문제 분석

브루트포스에 배정되어 있는 문제인만큼 모든 경우의 수를 구해야하는데 구현에 가까운 것마냥 만들어야 하는게 많았던 문제였다.

우선 5개의 그래프가 각각 시계 또는 반시계로 돌릴 수 있었고, 쌓는 순서가 무작위라 조합을 통해 순서가 담긴 조합을 구해야했다.

마지막으론 출발 지점으로부터 도착 지점까지 최소 거리도 구해야 하는 브루트포스 + 구현 + BFS 느낌이었다.

우선 각각의 그래프를 돌렸을 때 나올 수 있는 모양들을 그래프 넘버-로테이션 횟수 별로 dic에 담아주었다.

시계 방향으로 3번 돌리는 것은 반시계 방향으로 1번 돌린 결과니까 시계 방향으로만 돌린다는 가정하에 로테이션을 구현하였다.

 

로테이션을 구하는 방법으로는 0,0부터 출발하여 겉의 줄을 시계 방향으로 stack에 담아주었고,

스택에 다 담아주면 첫번째 요소부터 꺼내면서 0,4 부터 출발하여 시계 방향으로 돌면서 하나씩 그래프에 기록해주었다.

겉 줄을 마쳤다면 이제 안쪽도 로테이션 돌리면서 기록해주는 것으로 해결하였다.

dicGrpah 에는 [첫번째 그래프] : {

 0: 로테이션 안한 초기

 1: 1번 돌린 결과

 2:  2번 돌린 결과

 3: 3번 돌린 결과

}

이렇게 기록된다.

const dicGraphs = {};

const makeRotation = (curGrNumber) => {
    for (let i = 1; i < 4; i++) {
        const initGr = dicGraphs[curGrNumber][i - 1];
        const newGr = Array.from({ length: 5 }, () =>
            Array.from({ length: 5 }, () => -1)
        );
        newGr[2][2] = initGr[2][2];
        let [cs, ce] = [0, 5];
        let [rs, re] = [1, 4];

        while (re > rs && ce > cs) {
            const stack = [];
            for (let c = cs; c < ce; c++) {
                stack.push(initGr[rs - 1][c]);
            }
            for (let r = rs; r < re; r++) {
                stack.push(initGr[r][ce - 1]);
            }
            for (let c = ce - 1; c >= cs; c--) {
                stack.push(initGr[re][c]);
            }
            for (let r = re - 1; r >= rs; r--) {
                stack.push(initGr[r][cs]);
            }

            for (let r = cs; r < ce; r++) {
                newGr[r][re] = stack.shift();
            }
            for (let c = re - 1; c >= rs; c--) {
                newGr[ce - 1][c] = stack.shift();
            }
            for (let r = ce - 1; r >= cs; r--) {
                newGr[r][cs] = stack.shift();
            }
            for (let c = rs; c < re; c++) {
                newGr[cs][c] = stack.shift();
            }

            cs++;
            ce--;
            rs++;
            re--;
        }
        dicGraphs[curGrNumber][i] = newGr;
    }
};



for (let i = 0; i < 25; i += 5) {
    dicGraphs[`${i / 5}`] = {
        0: input.slice(i, i + 5).map((s) => s.split(' ').map(Number)),
    };
    makeRotation(i / 5);
}

이제 그래프가 쌓이는 순서를 넣어줄 조합을 구할 것인데 우선 쌓이는 그래프 넘버 조합을 구한 뒤에 각 그래프의 로테이션 횟수를 기록하여 최종 조합에 구할 것이다.

로테이션을 하지 않는 문제였다면 조합은 4-2-1-3-0 과 같이  [ idx 4 그래프 - idx 2 그래프 - idx 1 그래프 - idx 3 그래프 - idx 0 그래프] 이겠지만 각각의 그래프는 로테이션 가능하므로 

[ idx 4 그래프의 1번 로테이션 결과 -> idx 2 그래프 0번 로테이션 결과 -> idx 1 그래프 1번 로테이션 결과-> idx 3 그래프 3번 로테이션 결과-> idx 0 그래프 2번 로테이션 결과] 이러한 조합을 구해야 한다는 뜻이다.

아래는 그래프 넘버만을 통해 조합을 구한 것이다.

const tempCombis = [];

const makeTempCombi = (com) => {
    if (com.length === 5) {
        tempCombis.push(com);
        return;
    }
    for (let i = 0; i < 5; i++) {
        if (com.includes(i)) continue;
        makeTempCombi([...com, i]);
    }
};

makeTempCombi([]);

이제 위에서 구한 조합을 토대로 각각의 인덱스에 몇 번째 로테이션을 추가해주는 조합을 구한다.

const combinations = [];

const makeCombinations = (initCom, curCom, i) => {
    if (i === 5) {
        combinations.push(curCom);
        return;
    }

    const temp = [];

    for (let j = 0; j < 4; j++) {
        temp.push(`${initCom[i]}-${j}`);
    }

    for (const str of temp) {
        makeCombinations(initCom, [...curCom, str], i + 1);
    }
};

for (const combi of tempCombis) {
    makeCombinations(combi, [], 0);
}

이렇게 할 경우 조합 결과는 (5*4)*(4*4)*(3*4)*(2*4)*(1*4) = 122880 의 조합 길이가 나온다.

마지막으로 조합 결과를 탐색하면서 3차원 그래프를 만들고 0,0,0 에서부터 출발하여 4,4,4에 도착하는 최단 거리를 구하면 된다.

문제에서는 임의의 꼭지점에서부터 출발한다고 하지만 이미 각각의 로테이션 결과를 구했으므로 출발 지점은 0,0 만 고려하면 된다.

( 도착 지점은 출발 지점과 맞닿는 면이 아니어야 하므로 0,0,0에서 출발한 점은 4,0,0   4,0,4   4,4,0 이 아닌 4,4,4 에만 도착해야 한다 ) 

bfs를 구현하기 전에 dx,dy,dz 을 구하면

dx,dy는 다른 문제처럼 4방향 [0,1] [1,0] [-1,0] [0,-1] 로 동일하고 

dz는 현재 면 기준으로 위 아래로만 움직 일 수 있다. 즉 [ -1, 1 ] 인 것이다. 아래로 이동한 뒤에 이리저리 움직이다가 위로 다시 뚫고 올라가서 다시 방향을 움직이는 경우가 있으므로 위로 다시 올라가는 경우를 추가해야하는 것이다.

const dx = [0, 0, -1, 1];
const dy = [-1, 1, 0, 0];
const dz = [1, -1];

이제 다시 bfs 에 집중하면 위에서 구한 그래프 조합을 토대로 3차원 그래프를 구현한다.

for (const combi of combinations) {
    const gr = [];
    for ([grNum, roNum] of combi.map((s) => s.split('-').map(Number))) {
        gr.push(dicGraphs[grNum][roNum]);
    }
    //...
}

이제 방문을 기록할 visited와 다음 방문할 노드를 구하기 위한 큐를 만든다.

이때 0,0,0이 1이 아니라면 애초에 출발이 불가능하다는 것을 잊지말자.

const q = [];
const visied = Array.from({ length: 5 }, () =>
    Array.from({ length: 5 }, () => Array.from({ length: 5 }, () => -1))
);

if (gr[0][0][0] === 1) {
    q.push([0, 0, 0]);
    visied[0][0][0] = 0;
}

이제 bfs 방식으로 최단 거리를 찾고 결과와 비교하여 최솟값을 answer에 기록하면 된다.

while (q.length) {
    const [z, x, y] = q.shift();
    if (z === 4 && x === 4 && y === 4) {
        answer = Math.min(answer, visied[z][x][y]);

        break;
    }

    for (let i = 0; i < 4; i++) {
        const nx = x + dx[i];
        const ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5) continue;
        if (gr[z][nx][ny] === 0) continue;
        if (visied[z][nx][ny] !== -1) continue;
        visied[z][nx][ny] = visied[z][x][y] + 1;
        q.push([z, nx, ny]);
    }
    for (let i = 0; i < 2; i++) {
        const nz = z + dz[i];
        if (nz >= 5 || nz < 0) continue;
        if (gr[nz][x][y] === 0) continue;
        if (visied[nz][x][y] !== -1) continue;
        visied[nz][x][y] = visied[z][x][y] + 1;
        q.push([nz, x, y]);
    }
}

정답 코드

const dx = [0, 0, -1, 1];
const dy = [-1, 1, 0, 0];
const dz = [1, -1];

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const dicGraphs = {};

const makeRotation = (curGrNumber) => {
    for (let i = 1; i < 4; i++) {
        const initGr = dicGraphs[curGrNumber][i - 1];
        const newGr = Array.from({ length: 5 }, () =>
            Array.from({ length: 5 }, () => -1)
        );
        newGr[2][2] = initGr[2][2];
        let [cs, ce] = [0, 5];
        let [rs, re] = [1, 4];

        while (re > rs && ce > cs) {
            const stack = [];
            for (let c = cs; c < ce; c++) {
                stack.push(initGr[rs - 1][c]);
            }
            for (let r = rs; r < re; r++) {
                stack.push(initGr[r][ce - 1]);
            }
            for (let c = ce - 1; c >= cs; c--) {
                stack.push(initGr[re][c]);
            }
            for (let r = re - 1; r >= rs; r--) {
                stack.push(initGr[r][cs]);
            }

            for (let r = cs; r < ce; r++) {
                newGr[r][re] = stack.shift();
            }
            for (let c = re - 1; c >= rs; c--) {
                newGr[ce - 1][c] = stack.shift();
            }
            for (let r = ce - 1; r >= cs; r--) {
                newGr[r][cs] = stack.shift();
            }
            for (let c = rs; c < re; c++) {
                newGr[cs][c] = stack.shift();
            }

            cs++;
            ce--;
            rs++;
            re--;
        }
        dicGraphs[curGrNumber][i] = newGr;
    }
};

for (let i = 0; i < 25; i += 5) {
    dicGraphs[`${i / 5}`] = {
        0: input.slice(i, i + 5).map((s) => s.split(' ').map(Number)),
    };
    makeRotation(i / 5);
}

const tempCombis = [];

const makeTempCombi = (com) => {
    if (com.length === 5) {
        tempCombis.push(com);
        return;
    }
    for (let i = 0; i < 5; i++) {
        if (com.includes(i)) continue;
        makeTempCombi([...com, i]);
    }
};

makeTempCombi([]);

const combinations = [];

const makeCombinations = (initCom, curCom, i) => {
    if (i === 5) {
        combinations.push(curCom);
        return;
    }

    const temp = [];

    for (let j = 0; j < 4; j++) {
        temp.push(`${initCom[i]}-${j}`);
    }

    for (const str of temp) {
        makeCombinations(initCom, [...curCom, str], i + 1);
    }
};

for (const combi of tempCombis) {
    makeCombinations(combi, [], 0);
}

let INF = 1_000_000_000;

let answer = INF;

for (const combi of combinations) {
    const gr = [];
    for ([grNum, roNum] of combi.map((s) => s.split('-').map(Number))) {
        gr.push(dicGraphs[grNum][roNum]);
    }

    const q = [];
    const visied = Array.from({ length: 5 }, () =>
        Array.from({ length: 5 }, () => Array.from({ length: 5 }, () => -1))
    );

    if (gr[0][0][0] === 1) {
        q.push([0, 0, 0]);
        visied[0][0][0] = 0;
    }

    while (q.length) {
        const [z, x, y] = q.shift();
        if (z === 4 && x === 4 && y === 4) {
            answer = Math.min(answer, visied[z][x][y]);

            break;
        }

        for (let i = 0; i < 4; i++) {
            const nx = x + dx[i];
            const ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5) continue;
            if (gr[z][nx][ny] === 0) continue;
            if (visied[z][nx][ny] !== -1) continue;
            visied[z][nx][ny] = visied[z][x][y] + 1;
            q.push([z, nx, ny]);
        }
        for (let i = 0; i < 2; i++) {
            const nz = z + dz[i];
            if (nz >= 5 || nz < 0) continue;
            if (gr[nz][x][y] === 0) continue;
            if (visied[nz][x][y] !== -1) continue;
            visied[nz][x][y] = visied[z][x][y] + 1;
            q.push([nz, x, y]);
        }
    }
}

console.log(answer === INF ? -1 : answer);