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

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

 

 

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

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

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

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

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

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

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

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


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

 

 

문제 출처 🏠

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

13459번: 구슬 탈출

 

 

 

문제풀이 소감 🧑‍💻

 

저번에 구슬 탈출 2를 풀었었는데, 복습 겸으로 풀어보았다.

 

풀이가 생각날까봐 일부러 며칠뒤에 풀어주었는데, 효과가 있었음.

 

저번 풀이보다 조금 더 리팩터링을해서 진행했다. (ex. bfs 호출시 파라미터 스프레드 문법 사용) 

 

 

구슬 탈출 2와 비교하면 탈출을 할 수 있냐 없냐만 따지면 되어서 조금 더 쉽게 접근 할 수 있나 싶지만,

 

결국 10번을 넘느냐 안넘느냐를 똑같이 카운트해서 따져줘야하기 때문에 실제 체감 난이도는 별차이가 없을듯하다.

 

구슬탈출 2 문제보다 난이도가 낮게 측정된게 의외

 

 

 

 

요구사항 📋

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

 

 

 

 

*주의할 점과 해결 전략은 구슬 탈출 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

백준/ Gold 1 문제 , 백준 Node.js 자바스크립트 13460 구슬 탈출 2 [BFS, 구현]

 

 

 

 

 

정답 💯

 

 

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] = dq[0];
      dq = dq.splice(1);
      if (C > 10) break;
      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") return 1;
        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;
          dq.push([mrx, mry, mbx, mby, C + 1]);
        }
      }
    }
    return 0;
  };

  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];
  let [redBall, 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;

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

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