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

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

 

 

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

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

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

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

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

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

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

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


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

 

 

문제 출처 🏠

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

13460번: 구슬 탈출 2

 

 

 

문제풀이 소감 🧑‍💻

 

재밌어보여서 언젠가 꼭 풀어봐야지 했던 문제였는데, 오늘 풀어봤다.

 

어려울 것이라고 예상은 했지만, 어후.... 장난아니였다.

 

예외사항 한 부분 해결하는데 방문처리가 도무지 2차원 배열들로는 해결이 안되었다.

 

한참을 고민하다가 "아 !!! dict 키값으로 넣어볼까??" 생각이 들어서 적용해봤는데 성공~~

 

이 부분 말고도 처리해야할 부분이 더 많아서 준빡구현에 해당하는 문제다.

 

이 문제 시리즈가 4개인데 나머지 3개도 차근차근 풀어보겠다~

 

 

 

 

요구사항 📋

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

 

 

 

 

주의 ❗

 

 

요구사항 6. 동시에 둘 다 들어가도 실패

 

이 조건이 굉장히 까다롭다.

 

빨간공이 먼저들어가도 뒤따라 파란공이 들어오면 안된다.

 

한 번에 들어가는 경우 파란공이 같이 못들어오게 돌려가며 자리잡게한 뒤 빨간공만 들여보내게해야한다.

 

 

 

ex) 해당 예시

5 10
##########
#.#......#
##.......#
#OR..B.#.#
##########

 

정답 : 7

 

위 예시가 통과한다면, 어지간하면 맞을 것이다.

 

이 예시 통과시키는게 매우 빡셌음.

 

 

 

해결 전략 📝

 

 

우선 BFS로 빨간공 파란공을 동시에 돌려야 한다.

그러므로 move 함수를 따로 선언하여 움직임을 맡아주었다.

 

동시에 돌리는 이유는 겹치는 부분을 확인해주기 위해서다.

 

벽을 만나기 전까지 이동해야하므로 현재 위치에서 이동방향+ 한 값을 비교해주고

 

구멍이라면 해당 위치까지 가야하므로 현재위치를 비교해준다.

 

두 조건중 하나라도 해당된다면, 공의 움직임을 멈춘다.

 

 

만약 기울여서 이동시킨 공들의 위치가 서로 같다면, 한 공을 이동 방향의 반대 방향으로 한 칸 옮겨줘야한다.

 

이것을 효율적으로 확인하기 위해서 움직인 거리를 서로 확인해준다.

 

만약 움직인 거리가 더 많은쪽이 이전 위치로 이동해야한다. (그만큼 이전에 위치했었기 때문이다)

 

참고로 움직인 거리가 같은 경우는 없다.

 

이유는 같은 방향으로 똑같은 거리로 움직여서 겹치는 경우는 이전부터 겹쳐있었다는 뜻인데, 그런 경우는 없다.

 

 

 

 

나름 잘 생각했다고 느낀 코드다.

 

방문처리를 해주는 부분인데, 처음에 2개의 2차원 배열로 해결할려고 하니까 다른공이 이미 한 번 방문했다면, 다른 공이 방문하지 않은 위치에 와도 방문처리가 되어 큐에 값을 넣어주지 않는 오류가 있었다.

 

4차원 배열로 해결할까 했었는데, 코드가 너무 난잡해지는 것 같아 좀 더 효율적인 방법을 생각해보았다.

 

그러다가 단순 키값만 넣어서 한번이라도 값이 들어왔는지를 검사해주는 dict를 생각해내었고, 적용해보았다.

 

mrX,mrY,mbX,mbY 중에 하나라도 값이 달라지면 방문처리가 되지않기때문에 효과적이였다.

 

위에서 보여준 예시를 통과하기 위해선 이 방문처리를 제대로 해줘야한다.

 

 

 

 

 

정답 💯

 

 

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

let [input_NM, ...input_board] = input.map((v) => v.trim());
input_board = input_board.map((v) => v.split(""));
const [input_N, input_M] = input_NM.split(" ").map(Number);

function solution(N, M, board) {
  const bfs = (rx, ry, bx, by) => {
    let deque = [[rx, ry, bx, by, 1]];
    while (deque.length !== 0) {
      const [rX, rY, bX, bY, C] = deque[0];
      deque = deque.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 C;
        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;
          deque.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 += 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 [red, blue] = [[], []];

  board.forEach((line, i) => {
    line.forEach((v, j) => {
      if (v === "R") red = [i, j];
      if (v === "B") blue = [i, j];
    });
  });

  const visited = {};
  visited[`${red[0]}${red[1]}${blue[0]}${blue[1]}`] = true;

  return bfs(red[0], red[1], blue[0], blue[1]);
}

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