Softeer [Level 3] 나무 섭지 {언어 : JavaScript} [시간초과 해결]

문제 링크

https://softeer.ai/practice/7726

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(" "));
}).on('close', () => {
    const [n, m] = inputData[0].map((e) => Number(e));
    const board = inputData.slice(1, n+1).map((e) => e[0]);
    // N 남우 D 출구 G 유령 # 벽
    let [sr, sc, er, ec] = [0, 0, 0, 0];
    const ghosts = [];
    for (let r = 0; r < n; r++) {
        for (let c = 0; c < m; c++) {
            const tmp = board[r][c];
            if (tmp === "N") {
                [sr, sc] = [r, c];
            } else if (tmp === "D") {
                [er, ec] = [r, c];
            } else if (tmp === "G") {
                ghosts.push([r, c]);
            }
        }
    }
    // 방향 탐색 도구
    const isValid = (nr, nc) => {
        return 0 <= nr && nr < n && 0 <= nc && nc < m;
    }
    const dr = [-1, 1, 0, 0];
    const dc = [0, 0, -1, 1];

    
    // 남우가 탈출 지점까지 가는 최단 시간
    const nVisited = Array.from({length: n}, () => Array(m).fill(-1));
    const nq = [[sr, sc]];
    nVisited[sr][sc] = 0;
    while (nq.length) {
        const [r, c] = nq.shift();
        for (let d = 0; d < 4; d++) {
            const nr = r + dr[d];
            const nc = c + dc[d];
            if (isValid(nr, nc) && nVisited[nr][nc] === -1 && board[nr][nc] !== "#") {
                nq.push([nr, nc]);
                nVisited[nr][nc] = nVisited[r][c] + 1;
            }
        }
    }
    
    // 유령이 탈출 지점까지 가는 최단 시간
    const shortGhost = ghosts.reduce((shortCut, [gr, gc]) => {
        const tmp = Math.abs(gr-er) + Math.abs(gc-ec);
        if (shortCut > tmp) {
            return tmp;
        }
        return shortCut;
    }, n+m+1)

    const answer = nVisited[er][ec] === -1 ? "No" : shortGhost > nVisited[er][ec] ? "Yes" : "No";
    console.log(answer);
    process.exit(0);
});

풀이 방법

1. 남우가 탈출하는데 걸리는 시간을 bfs 알고리즘과 dp를 사용해서 기록한다.
   • 현재 지점에서 다음 지점(상하좌우 중)이 유효한지 확인한다.
     • 격자 안에 있는지, 방문하지 않은 곳인지, 벽이 아닌지 확인
   • 유효한 곳이라면 이동하고 전에 있었던 곳에 도달한 시간에 +1을 추가하여 다음 곳에 저장한다.
     • nVisited[nr][nc] = nVisited[r][c] + 1;
   • 이렇게 n*m 격자를 모두 탐색한다.
2. 유령은 벽을 통과한다.
   • 즉, bfs 알고리즘을 사용하지 않아도 된다.
   • 왜냐하면 어차피 최단 거리이자 최단 시간은 출구로 부터 유령까지의 거리이기 때문이다.
   • 유령마다 출구까지의 거리를 측정해서 최단 시간을 갱신한다.
3. 유령이 출구까지 도달하는 것이 빠른지 남우가 출구까지 도달하는 것이 빠른지 비교한다.
   • 이때 남우가 출구까지 도달하지 못했다면 nVisited[er][ec]값은 -1이고 "No"를 출력한다.
   • 남우가 빠르다는 말은 남우의 거리가 유령의 거리보다 작다는 말이므로 "Yes"를 출력한다.
   • 유령의 거리가 남우의 거리보다 작거나 같다면 남우가 출구에 도달해서 유령을 마주치거나 출구에 도달하기 전에 유령을 만난다는 말이므로 "No"를 출력한다.
4. 마지막으로 answer를 출력하면 끝!

느낀점

• 시간을 visited에 누적해서 더하는 방식은 다이나믹 프로그래밍으로 동적 계획법에 해당한다.
  • 메모이제이션을 했다는 말이다.
• 특히나 중요한 부분은 유령을 bfs로 돌렸다가 시간초과가 나거나 오답이 난 부분인데, 어차피 유령은 벽을 통과한다라는 점을 간과한 것이 잘못이었다.
• 만약 시간초과가 난다면 유령을 하나하나 bfs를 돌리지 않았는지 확인해보면 좋을 것 같다.