4179 불!

문제

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.

불은 각 지점에서 네 방향으로 확산된다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

J는 입력에서 하나만 주어진다.

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

=====

문제 분석

불이 시간마다 번질 수 있는 것을 기록하는 fireVisited 를 선언하여 시간을 적은 뒤

지훈이가 움직일 수 있는 공간을 탐색하는 것으로 만들었다. 

x,y라는 위치에서 불이 10초가 경과한 뒤 번지는 위치라면 fireVisited[x][y]=10 일텐데 만약 지훈이가 x,y를 10초 이상부터 닿는 위치라면 그 곳은 갈 수 없는 것이다.

오답 노트

 1. 문제 입력 지문에 나와 있듯 지훈이의 위치인 J는 하나만 주어진다는 것에서 눈치 챘어야 했는데, 지훈이는 하나만 주어지지만 불은 여러개가 주어질 수 있다는 것을 놓쳐서 틀렸었다.

2. 위의 방식이 틀린 건 아니지만 문제 분석에서 적은 fireVisited를 따로 선언하는 것 대신 불과 지훈이 위치 모두를 큐에 넣은 다음에 불이라면 그래프의 해당 위치 값을 F로 변환하면서 탐색 했어도 됐을 것 같다. (물론 초반에 불부터 다 넣고 그 뒤에 지훈이의 위치를 큐에 넣어준다는 전제하에) ---->  정답 코드 두번 째가 이 방식으로 작성해본거임

정답 코드 (2가지)

1. 문제 분석에 적은 대로 불의 시간에 따른 위치를 기록하면서 푼 방식 => bfs를 두번 돌린다.

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

const findStart = (n, m, char, gr) => {
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (gr[i][j] === char) {
                return [i, j];
            }
        }
    }
};
const main = (input) => {
    const [n, m] = input[0].split(' ').map((v) => +v);
    const gr = [];

    for (let i = 1; i < input.length; i++) {
        gr.push(input[i].split(''));
    }

    const [peopleSx, peopleSy] = findStart(n, m, 'J', gr);

    const fire = [];
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (gr[i][j] === 'F') {
                fire.push([i, j]);
            }
        }
    }

    const fireVisited = Array.from({ length: n }, () =>
        Array.from({ length: m }).fill(INF)
    );
    const q = [];

    fire.forEach(([x, y]) => {
        q.push([x, y]);
        fireVisited[x][y] = 0;
    });

    while (q.length) {
        const [cx, cy] = q.shift();
        for (let i = 0; i < 4; i++) {
            const nx = cx + dx[i];
            const ny = cy + dy[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (fireVisited[nx][ny] !== INF) continue;
            if (gr[nx][ny] === '#') continue;
            fireVisited[nx][ny] = fireVisited[cx][cy] + 1;
            q.push([nx, ny]);
        }
    }
    const qq = [[peopleSx, peopleSy]];
    const visited = Array.from({ length: n }, () =>
        Array.from({ length: m }).fill(-1)
    );
    visited[peopleSx][peopleSy] = 0;
    let answer = INF;
    while (qq.length) {
        const [cx, cy] = qq.shift();
        if (cx === 0 || cx === n - 1 || cy === 0 || cy === m - 1) {
            answer = Math.min(answer, visited[cx][cy] + 1);
            continue;
        }
        for (let i = 0; i < 4; i++) {
            const nx = cx + dx[i];
            const ny = cy + dy[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (gr[nx][ny] === '#') continue;
            if (visited[nx][ny] !== -1) continue;
            if (fireVisited[nx][ny] <= visited[cx][cy] + 1) continue;
            visited[nx][ny] = visited[cx][cy] + 1;
            qq.push([nx, ny]);
        }
    }
    console.log(visited);
    if (answer === INF) {
        console.log('IMPOSSIBLE');
    } else {
        console.log(answer);
    }
};

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

main(input);

2. 오답노트의 2번 문항에서 적은 대로 탐색 한번으로 문제를 해결한 코드

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

const findStart = (n, m, char, gr) => {
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (gr[i][j] === char) {
                return [i, j];
            }
        }
    }
};
const main = (input) => {
    const [n, m] = input[0].split(' ').map((v) => +v);
    const gr = [];

    for (let i = 1; i < input.length; i++) {
        gr.push(input[i].split(''));
    }
    visited = Array.from({ length: n }, () =>
        Array.from({ length: m }).fill(-1)
    );

    const q = [];
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (gr[i][j] === 'F') {
                q.push([i, j, true]);
            }
        }
    }
    for (let i = 0; i < n; i++) {
        let isBreak = false;
        for (let j = 0; j < m; j++) {
            if (gr[i][j] === 'J') {
                q.push([i, j, false]);
                visited[i][j] = 0;
                isBreak = true;
                break;
            }
        }
        if (isBreak) break;
    }

    while (q.length) {
        const [cx, cy, isFire] = q.shift();
        if (!isFire && (cx === 0 || cy === 0 || cx === n - 1 || cy === m - 1)) {
            console.log(visited[cx][cy] + 1);
            process.exit(0);
        }
        for (let i = 0; i < 4; i++) {
            const nx = cx + dx[i];
            const ny = cy + dy[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (gr[nx][ny] === '#') continue;
            if (isFire) {
                if (gr[nx][ny] === '.') {
                    gr[nx][ny] = 'F';
                    q.push([nx, ny, true]);
                }
            } else {
                if (visited[nx][ny] !== -1) continue;
                if (gr[nx][ny] === 'F') continue;
                visited[nx][ny] = visited[cx][cy] + 1;
                q.push([nx, ny, false]);
            }
        }
    }
    console.log('IMPOSSIBLE');
};

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

main(input);

아래 코드로 풀었더니 시간이 4토막이 났다