[JS] 백준 13460번 : 구술 탈출 2

 

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

13460번: 구슬 탈출 2

 

 

📋풀이방법

1.BFS방법을 이용

2. queue에는 [빨간공좌표, 파란공 좌표, 기울인 수, 이전에 기울였던 방향을 알려주는 숫자]

3. 4방향으로 기울이는 걸 반복함

4. 빨간 구슬을 정해진 한 방향으로 벽이있는 곳까지 움직임

  -움직이는 와중에 "O"를 발견하면 구멍에 들어감을 표시해줌(redIn)

  -벽을 만나면 반복을 빠져나오고 움직인 좌표에서 한칸 뒤로가줌(벽이있는 좌표가아닌 벽 이전의 공간으로)

  -움직인 횟수 저장(redMove)

5. 파란 구슬을 정해진 한 방향으로 벽이 있는 곳까지 움직임

  -움직이는 와중에 "O"를 발견하면 구멍에 들어감

  -벽을 만나면 반복을 빠져나오고 움직인 좌표에서 한칸 뒤로가줌(벽이있는 좌표가아닌 벽 이전의 공간으로)

  -움직인 횟수 저장(blueMove)

6.이동을 완료 후 두 공의 좌표가 같을 때 (같은 공간에 있으면 안되는 조건)

  -움직인횟수가 더 많은 공아 한칸 뒤로 감

7. 만약 redIn이 true고, blueIn이 false면 게임이 끝난 것이르모 전달된 cnt에 +1해서 answer에 저장

8. 만약 둘다 아예 움직이지 않았다면 큐에 넣지않고 continue한다(정해진 기울이기로는 움직일 수없으므로 이후 기울이는  경우의 수는 필요가 없음)

9. 만약 blueIn만 false면 파란공이 안들어 갔으므로 게임은 계속 진행가능 - 파랑공이 true면 더이상 탐색해도 의미없음

-> queue에 [해당 기울임을 완료한 좌표들과 cnt , 기울였던 방향을 알려주는 숫자]를 넣어줌

 

 

🤟내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input=input.replace(/\r/g,"").split("\n");

let [N,M]=input.shift().split(" ").map(Number);
let arr=[];
for(var i=0;i<N;i++){
    arr.push(input.shift().split(""));
}

let dx=[1,0,0,-1];
let dy=[0,1,-1,0];
let red=[];
let blue=[];

for(var i=0;i<N;i++){
    for(var j=0;j<M;j++){
        if(arr[i][j]=="R") red.push(i,j)
        else if(arr[i][j]=="B") blue.push(i,j);
    }
}

let answer=-1;

let queue=[];
queue.push([red,blue,0,-1]);

while(queue.length){
    let [Rw,Bw,cnt,d]= queue.shift();
    for(var i=0;i<4;i++){
        if (i == d || cnt >= 10) continue;
        let Bnx=0,Bny=0,Rnx=0,Rny=0;
        let redMove=0, blueMove=0;
        let redIn = false, blueIn = false;
        
        // 빨간구슬 이동
        Rnx = Rw[1];
        Rny = Rw[0];
        while (arr[Rny][Rnx] != '#'){
            Rnx += dx[i]
            Rny += dy[i];
            redMove ++;
            // 빨간 구슬이 구멍에 들어감
            if (arr[Rny][Rnx] == 'O'){
                redIn = true;
                break;
            }
        }
        Rnx -= dx[i]
        Rny -= dy[i];

        // 파란구슬 이동
        Bnx = Bw[1];
        Bny = Bw[0];
        while (arr[Bny][Bnx] != '#'){
            Bnx += dx[i];
            Bny += dy[i];
            blueMove++;
            // 파란 구슬이구멍에 들어감
            if (arr[Bny][Bnx] == 'O'){
                blueIn = true;
                break;
            }
        }
        Bnx -= dx[i];
        Bny -= dy[i];

        // 이동 후 두 공의 좌표가 같다면 더 많이 움직인 공을 한 칸 뒤로 옮김
        if (Rnx == Bnx && Rny == Bny){
            if (redMove < blueMove){
                Bnx -= dx[i];
                Bny -= dy[i];
            }
            else {
                Rnx -= dx[i];
                Rny -= dy[i];
            }
        }
        // 게임이 끝나는 조건
            if (redIn && !blueIn){
                answer = cnt+1;
                return console.log(answer);
            }
            // 아예 이동하지 않았으면 다시 queue에 넣어주지 않는다
            else if (Rnx == Rw[1] && Rny == Rw[0] && Bnx == Bw[1] && Bny == Bw[0]){
                continue;
            }
            // 파란공이 구멍에 들어가지 않은 경우만 탐색 진행
            else if (!blueIn){
                queue.push([[Rny, Rnx], [Bny, Bnx], cnt+1,i]);
            }

    }

}
console.log(answer)

 

 

💢어려웠던점

1. 문제 풀이 순서를 파악하지 못했고, 생각해낸 풀이방법을 코드로 옮기지못했다.

2. 다른 코드를 리팩토링하여 문제를 풀어냈다.

2. 이 문제는 한번씩 봐야할 것 같다.