1194 달이 차오른다, 가자 (자바스크립트)

문제

지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.

민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다.

하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.

영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.

민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다.

• 빈 칸: 언제나 이동할 수 있다. ('.')
• 벽: 절대 이동할 수 없다. ('#')
• 열쇠: 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. ('a', 'b', 'c', 'd', 'e', 'f')
• 문: 대응하는 열쇠가 있을 때만 이동할 수 있다. ('A', 'B', 'C', 'D', 'E', 'F')
• 민식이의 현재 위치: 빈 곳이고, 민식이가 현재 서 있는 곳이다. ('0')
• 출구: 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. ('1')

달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.

민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

=====

문제 풀이

bfs 방식으로 탐색을 진행할건데 대문자에 도착했을 경우에는 열쇠가 필요했다. 

따라서 열쇠의 가지고 있냐를 기준으로 방문 체크를 달리해줄 필요가 있었다.

알파벳이 총 7개 뿐이므로 열쇠를 가지고 있냐를 비트마스크로 체크해줬다. 

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

큐에는 현재 위치, 가지고 있는 열쇠의 조합을 나타낼 비트마스크, 이동 횟수를 담아준다.

#을 만난다면 패스,

.을 만나면 visited[nx][ny][hasKey] 가 true인지 체크. true라면 방문 했었던 것이므로 패스

대문자를 만났을 땐 대문자의 아스키 코드에서 65를 뺸뒤 그만큼 1<<num을 하고 hasKey와 & 연산을 통해 열쇠를 갖고 있는지 체크해주고 동시에 방문했던 경로인지도 체크. 

소문자를 만났을 땐, 열쇠가 여러개 있을 수 있으므로 그저 | 연산을 통해 기존 키에 추가해주고 방문 체크 

'1' 을 만나면 프로그램 종료 

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

const [n, m] = input[0].split(' ').map(Number);
const gr = input.slice(1).map((s) => s.split(''));
// 대문자 문, 소문자 열쇠

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

const init = () => {
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (gr[i][j] === '0') {
                gr[i][j] = '.';
                return [i, j];
            }
        }
    }
};
const [sx, sy] = init();
const q = [[sx, sy, 0, 0]];
visited[sx][sy][0] = true;

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

const checkIsUpper = (char) => {
    const num = char.charCodeAt();
    if (num >= 65 && num <= 91) {
        return true;
    }
    return false;
};
while (q.length) {
    const [x, y, hasKey, cnt] = q.shift();
    // console.log(x, y, hasKey, cnt);

    for (let i = 0; i < 4; i++) {
        const nx = x + dx[i];
        const ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
        if (gr[nx][ny] === '#') continue;
        if (gr[nx][ny] === '1') {
            console.log(cnt + 1);
            process.exit(0);
        }
        if (gr[nx][ny] === '.') {
            if (visited[nx][ny][hasKey]) continue;
            visited[nx][ny][hasKey] = true;
            q.push([nx, ny, hasKey, cnt + 1]);
            continue;
        }
        const alpha = gr[nx][ny];
        if (checkIsUpper(alpha)) {
            const num = alpha.charCodeAt() - 65;
            if ((hasKey & (1 << num)) === 0) continue;
            if (visited[nx][ny][hasKey]) continue;
            visited[nx][ny][hasKey] = true;
            q.push([nx, ny, hasKey, cnt + 1]);
        } else {
            const num = alpha.charCodeAt() - 97;
            const getKey = hasKey | (1 << num);
            if (visited[nx][ny][getKey]) continue;
            visited[nx][ny][getKey] = true;
            q.push([nx, ny, getKey, cnt + 1]);
        }
    }
}
console.log(-1);