백준/ Gold 4 문제 , 백준 Node.js 자바스크립트 4179 불!

백준/ Gold 4 문제 , 백준 Node.js 자바스크립트 4179 불!

 

 

✔️Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감 🧑‍💻
1. 최상
2. 상
3. 중
4. 하


이해도 🙆‍♂️
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함

 

 

문제 출처 🏠

https://www.acmicpc.net/problem/4179

4179번: 불!

 

 

 

문제풀이 소감 🧑‍💻

문제 자체는 어렵지 않았지만, node.js로 풀면서 내가 그동안 착각하고 있었던 점을 알게된 문제다.

 

조금 길어질 것 같으니 따로 포스팅해서 첨부하겠다.

 

https://bmy1320.tistory.com/entry/TIL1-%ED%81%90%EB%A5%BC-%EA%B5%AC%ED%98%84%ED%95%A0-%EB%95%8C%EB%8A%94-splice-%EB%B3%B4%EB%8B%A8-shift

TIL.1 - 큐를 구현할 때는 splice 보단 shift

 

 

 

 

요구사항 📋

 

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

 

• 불은 상하좌우로 동시에 움직인다.
• 불과 벽은 지훈이 지나갈 수 없다.
• 더이상 지훈이 움직일 수 없거나, 아무리 움직여도 미로를 탈출할 수 없다면 'IMPOSSBLE' 를 출력한다.

 

 

 

주의 ❗

 

불을 먼저 이동 시켜준다.

 

이미 지훈의 위치는 큐에 담겨있기때문에 현재위치가 지워져도 아무런 상관이 없다.

 

오히려 지훈을 먼저 이동 시키면 틀린 코드가 되었다.

 

 

추가로, 불이 꼭 존재한다는 법도 없고 불이 꼭 한 군데에서만 생긴다는 법도 없다.

 

모두 고려하자.

 

 

해결 전략 📝

 

지훈의 위치는 한 곳이지만, 불의 위치는 여러곳일 수도 있다. 그러므로 배열을 만들어서 초기 불의 위치를 모두 담아준다.

 

deque에 차례로 담아주게 되면 한 번의 Cycle을 돌면서 지훈과 불이 이동할 수 있는 위치를 한번씩 모두 움직여주게 된다.

 

큐에서 지훈에 대한 정보가 끝나는 지점이 한 Cycle이 끝나는 지점이다. 

 

ex)

 

deque = [ 불 불 불 불 지훈 지훈 / (1 Cycle) / 불 불 ....불 지훈 ...지훈 / (2 Cycle) / .... ]

 

 

 

우리가 bfs 시간을 줄여주기위해 꼭 확인해줘야하는 것이 있는데, 바로 지훈이 계속 움직일 수 있는지이다.

 

지훈의 큐, 불의 큐를 각각 따로 만들어서 확인하는 방법도 있겠지만,

 

나는 하나의 큐를 사용해가면서 지훈의 움직임을 따로 확인해주는 방법으로 풀었다.

 

cntJmove 이라는 변수를 선언하여 초깃값 1을 설정한다.

 

이 변수가 하는 역할은 deque에 지훈의 정보다 몇개가 담겨있는지를 나타내주는 역할이라고 생각하면 된다.

 

만약 cntJmove 가 3이라면 현재 deque에 지훈의 정보가 3개 담겨있다는 뜻이다.

 

 

그렇다면 지훈이 더이상 움직일 수 없는 경우라면?

 

 

당연히 cntJmove의 값은 0일 것이다. 이럴때는 queue 를 계속 돌려주는 것이 의미없으므로 break 를 걸어 탈출시켜준다.

 

지훈이 이동하다가 불에 먹혀 더이상 큐에 지훈에 대한 정보가 들어가지 않거나 벽에 가로막혀 지훈이 더이상 움직일 수 없는 등 이런 예외사항들을 모두 체크해줄 수 있다.

 

만약 queue 에 담긴 값을 꺼냈을 때 지훈의 위치가 각 행이나 열의 끝지점에 서 있다면, 다음 움직임에 탈출할 수 있는 경우이므로 이 경우는 if 조건문을 통해 걸러줘서 현재까지 움직인 값인 C 값에 +1 을 해줘서 return 해주면 된다.

 

 

 

 

 

 

정답 💯

 

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [input_N, input_M] = input[0].split(" ").map(Number);
input.shift();
const [...input_board] = input.map((v) => v.split(""));

function solution(N, M, board) {
  const bfs = (jihoon, fire) => {
    let cntJMove = 1;
    dq = [];
    fire.forEach((v) => {
      dq.push([...v, "F", 0]);
    });
    dq.push([...jihoon, "J", 0]);
    while (dq.length !== 0) {
      const [x, y, mover, cnt] = dq[0];
      dq.shift();
      if (mover === "J") cntJMove -= 1;
      if (x === 0 || x === N - 1 || y === 0 || y === M - 1) {
        if (mover === "J") return cnt + 1;
      }
      for (let i = 0; i < 4; i++) {
        const [mx, my] = [x + dr_x[i], y + dr_y[i]];
        if (mx < 0 || mx >= N || my < 0 || my >= M) continue;
        if (mover === "J") {
          if (board[mx][my] === ".") {
            board[mx][my] = "J";
            dq.push([mx, my, "J", cnt + 1]);
            cntJMove += 1;
          }
        } else if (mover === "F") {
          if (board[mx][my] === "." || board[mx][my] === "J") {
            board[mx][my] = "F";
            dq.push([mx, my, "F"]);
          }
        }
      }
      if (cntJMove <= 0) break;
    }
    return "IMPOSSIBLE";
  };
  const dr_x = [-1, 0, 1, 0];
  const dr_y = [0, 1, 0, -1];
  let [jihoonInfo, fireInfo] = [[], []];
  board.forEach((line, i) => {
    line.forEach((v, j) => {
      if (v === "J") jihoonInfo = [i, j];
      if (v === "F") fireInfo.push([i, j]);
    });
  });

  return bfs(jihoonInfo, fireInfo);
}

console.log(solution(input_N, input_M, input_board));