🔴 문제
🟡 Sol
const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [rc, ...inputs] = fs.readFileSync(path).toString().trim().split('\n');
const [r, c] = rc.split(' ').map(Number);
const map = inputs.map((it) => it.split(''));
const fire = inputs.map((it) => it.split(''));
const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];
const fireQ = [];
const q = [];
// 불의 좌표와 지훈이의 좌표값 구하기
for (let i = 0; i < r; i++) {
for (let j = 0; j < c; j++) {
if (map[i][j] === '#') continue;
if (map[i][j] === 'J') {
q.push([i, j]);
map[i][j] = 1;
fire[i][j] = '.';
}
if (map[i][j] === 'F') {
fireQ.push([i, j]);
fire[i][j] = 1;
} else fire[i][j] = '.';
}
}
// 불의 최단시간 계산
while (fireQ.length) {
const [x, y] = fireQ.shift();
for (let i = 0; i < 4; i++) {
const nx = x + dx[i];
const ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
if (fire[nx][ny] === '#') continue;
if (fire[nx][ny] === '.') {
fire[nx][ny] = fire[x][y] + 1;
fireQ.push([nx, ny]);
}
}
}
// 지훈이가 탈출할 수 있는지 확인
while (q.length) {
const [x, y] = q.shift();
for (let i = 0; i < 4; i++) {
const nx = x + dx[i];
const ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
if (map[nx][ny] === '#') continue;
if (map[nx][ny] === '.') {
if (fire[nx][ny] === '.' || map[x][y] + 1 < fire[nx][ny]) {
map[nx][ny] = map[x][y] + 1;
q.push([nx, ny]);
} else {
map[nx][ny] = 'F';
}
}
}
}
let isEscape = [];
// 탈출 여부 확인
for (let i = 0; i < r; i++) {
if (typeof map[i][0] === 'number') isEscape.push(map[i][0]);
if (typeof map[i][c - 1] === 'number') isEscape.push(map[i][c - 1]);
}
for (let i = 0; i < c; i++) {
if (typeof map[0][i] === 'number') isEscape.push(map[0][i]);
if (typeof map[r - 1][i] === 'number') isEscape.push(map[r - 1][i]);
}
if (isEscape.length === 0) {
console.log('IMPOSSIBLE');
} else {
console.log(Math.min(...isEscape));
}
🟢 풀이
⏰ 소요한 시간 : 2시간 + 풀이
처음에는 지훈이의 좌표와 불을 동시에 큐에 넣었다. 같이 움직이니께 ...
그러다 유튜브에서 아이디어를 얻어냈다.
유튜브에서 얻어낸 아이디어는 일단 불이 각 좌표에 도달하는 최단시간(가중치)을 구해놓고 지훈이가 최단시간보다 더 이르게 도착하면 그 좌표를 지나갈 수 있다는 것이다.
이 아이디어에 맞게 풀이했더니 맞았습니다를 받을 수 있었다.
아이디어에 기반해서 코드를 세세하게 풀어보자면, 먼저 불의 좌표를 사용해서 가중치를 구해줘야 하니까 불의 좌표를 모두 구해서 큐에 넣는다. 그리고 좀이따가 지훈이의 좌표로도 가중치를 구해야 하므로 지훈이의 좌표도 찾아 큐에 넣어준다. 이때 불이 있던 위치와 지훈이가 있던 위치는 1이라는 초기값을 넣어주어 bfs에서 가중치를 구할 수 있도록 했다.
그 후 불의 가중치를 구해주는 BFS 로직을 작성한다. 지훈이가 있건, 없건 벽이 없으면 모든 위치를 갈 수 있다는 가정이다. 이 BFS 로직을 다 돌고나면 fire라는 이차원 배열에는 각 좌표에 불이 얼마만에 도착할 수 있는지에 대한 정보가 들어있다.
이 정보를 가지고 지훈이가 탈출할 수 있는지에 대한 BFS 로직을 수행해준다. 불의 로직과 비슷하지만 아래와 같은 케이스에 지훈이는 벽으로 둘러싸여 있기 때문에 불의 방해 없이 탈출이 가능한데 이 경우도 지훈이가 전진할 수 있도록 체크해줘야 한다.
5 5
.....
####.
..J#F
####.
.....이후 가장자리를 돌면서 숫자값이 있는지 없는지 확인한다. 숫자값이 있다면 탈출을 했다는 의미이므로 isEscape 배열에 추가해준 뒤 최종적으로 배열의 길이에 따라 조건을 걸어 결과값을 출력해주면 된다.
나는 두번의 틀렸습니다를 받았는데, 첫번째 이유는 위에서 언급한 벽으로 둘러싸인 케이스를 생각하지 못했고, 두번째는 최종 결과값이 여러개여서 그중 최소값을 골라야 된다는 것을 생각하지 못했다.
그리고 몰랐던 사실이 있는데 위의 경우 Number.isNaN()을 사용하는 것보다 typeof 키워드를 사용해 숫자인지 아닌지 판단하는것이 더 적합하다는 사실이다.
🔵 Ref
