백준/ Gold 1 문제 , 백준 Node.js 자바스크립트 15653 구슬 탈출 4

백준/ Gold 1 문제 , 백준 Node.js 자바스크립트 15653 구슬 탈출 4

 

 

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

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

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

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

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

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

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

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


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

 

 

문제 출처 🏠

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

15653번: 구슬 탈출 4

 

 

문제풀이 소감 🧑‍💻

구슬 탈출 2를 풀 때 고생해서 그런지 구슬 탈출 1,3,4 문제들은 큰 어려움 없이 잘 풀렸다.

 

구슬 탈출 2 풀이를 메인으로 문제마다 요구사항에 맞게 조건만 조금씩만 변경하면 모두 해결된다.

 

따라서, 구슬 탈출 2 문제를 먼저 학습하고 오기를 추천한다.

 

이 문제는 구슬 탈출 2 풀이에서 기울이기 제한만 없애주면 되는 문제다.

 

 

 

 

 

요구사항 📋

1. 세로 N, 가로 M
2. 왼쪽, 오른쪽, 위쪽, 아래쪽으로 기울이기 동작 가능
3. 공은 동시에 움직인다.
4. 빨간 구슬이 구멍에 들어가면 성공
5. 파란 구슬이 구멍에 들어가면 실패
6. 동시에 둘다 들어가도 실패
7. 동시에 같은 칸에 같이 있을 수 는 없다.
8. 빨간 구슬을 뺄 수 있다면, 몇 번만에 뺐는지를 출력한다.
9. 만약, 아무리 움직여도 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.

 

 

 

 

*주의할 점과 해결 전략은 구슬 탈출 2 포스팅을 참고해주시길 바랍니다.

 

https://bmy1320.tistory.com/entry/%EB%B0%B1%EC%A4%80-Gold-1-%EB%AC%B8%EC%A0%9C-%EB%B0%B1%EC%A4%80-Nodejs-%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-13460-%EA%B5%AC%EC%8A%AC-%ED%83%88%EC%B6%9C-2-BFS-%EA%B5%AC%ED%98%84

 

 

 

 

 

 

 

정답 💯

 

 

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 = (rx, ry, bx, by) => {
    let dq = [[rx, ry, bx, by, 1]];
    while (dq.length !== 0) {
      const [rX, rY, bX, bY, C] = dq[0];
      dq = dq.splice(1);
      for (let i = 0; i < 4; i++) {
        let [mrx, mry, rc] = move(rX, rY, dr_x[i], dr_y[i]);
        let [mbx, mby, rb] = move(bX, bY, dr_x[i], dr_y[i]);
        if (board[mbx][mby] === "O") continue;
        if (board[mrx][mry] === "O") return C;
        if (mrx === mbx && mry === mby) {
          if (rc > rb) {
            [mrx, mry] = mediate(mrx, mry, dr_x[i], dr_y[i]);
          } else if (rc < rb) {
            [mbx, mby] = mediate(mbx, mby, dr_x[i], dr_y[i]);
          }
        }
        const key = `${mrx}${mry}${mbx}${mby}`;
        if (visited[key] === undefined) {
          visited[key] = true;
          dq.push([mrx, mry, mbx, mby, C + 1]);
        }
      }
    }
    return -1;
  };

  const move = (x, y, drX, drY) => {
    let cnt = 0;
    while (board[x + drX][y + drY] !== "#" && board[x][y] !== "O") {
      [x, y, cnt] = [x + drX, y + drY, cnt + 1];
    }

    return [x, y, cnt];
  };

  const mediate = (x, y, drX, drY) => {
    return [x - drX, y - drY];
  };

  const dr_x = [-1, 0, 1, 0];
  const dr_y = [0, 1, 0, -1];
  const visited = {};
  let [redBall, blueBall] = [[], []];
  board.forEach((line, i) => {
    line.forEach((v, j) => {
      if (v === "B") blueBall = [i, j];
      if (v === "R") redBall = [i, j];
    });
  });
  visited[`${redBall[0]}${redBall[1]}${blueBall[0]}${blueBall[1]}`] = true;

  return bfs(...[...redBall, ...blueBall]);
}

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