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

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

 

 

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

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

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

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

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

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

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

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


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

 

 

문제 출처 🏠

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

15644번: 구슬 탈출 3

 

 

 

문제풀이 소감 🧑‍💻

 

구슬 탈출2 를 잘 풀었다면, 어려움 없이 풀 수 있는 문제이다.

 

기울인 방향만 잘 저장해나아가면 되는데, deque에 기울인 방향을 담을 배열을 하나 더 추가해주면 해결된다.

 

 

 

요구사항 📋

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

 

 

 

추가 해결 전략 📝

 

 

dq에 넣어줄 값만 방향을 추가하여 저장한다. 

 

이외의 경우들은 기울임에 해당되지 않는 경우이므로 무시한다.

 

 

 

주의❗

 

구멍에 들어갈 경우는 바로 종료되기때문에 현재 기울인 방향을 추가적으로 저장한 뒤에 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.trim().split(""));

function solution(N, M, board) {
  const bfs = (rx, ry, bx, by) => {
    dq = [[rx, ry, bx, by, 1, []]];
    while (dq.length !== 0) {
      const [rX, rY, bX, bY, C, dir] = dq[0];
      if (C > 10) break;
      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, bc] = move(bX, bY, dr_x[i], dr_y[i]);
        if (board[mbx][mby] === "O") continue;
        if (board[mrx][mry] === "O") {
          dir.push(direction[i]);
          return [C, dir];
        }
        if (mrx === mbx && mry === mby) {
          if (rc > bc) {
            [mrx, mry] = mediate(mrx, mry, dr_x[i], dr_y[i]);
          } else if (rc < bc) {
            [mbx, mby] = mediate(mbx, mby, dr_x[i], dr_y[i]);
          }
        }

        let key = `${mrx}${mry}${mbx}${mby}`;
        if (visited[key] === undefined) {
          visited[key] = true;
          const newDir = [...dir, direction[i]];
          dq.push([mrx, mry, mbx, mby, C + 1, newDir]);
        }
      }
    }
    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 direction = ["U", "R", "D", "L"];
  let redBall = [];
  let blueBall = [];
  board.forEach((line, i) => {
    line.forEach((v, j) => {
      if (v === "R") redBall = [i, j];
      if (v === "B") blueBall = [i, j];
    });
  });

  const visited = {};
  visited[`${redBall[0]}${redBall[1]}${blueBall[0]}${blueBall[1]}`] = true;
  const [C, dir] = bfs(...[...redBall, ...blueBall]);
  if (C === -1) console.log(-1);
  else {
    console.log(C);
    console.log(dir.join(""));
  }
}

solution(input_N, input_M, input_board);