[백준] 13460 - 구슬 탈출2 (java)

13460번: 구슬 탈출 2

---

 

DP문제집을 풀다가 재미있어 보이는 문제가 있어서 풀기시작했다.

풀면 풀수록 생각할 것이 더 생기는 문제였다.

 

결국 풀기는 했지만 실행시간이 엄청 오래걸렸다...

(이전에 이동한 위치를 또 갈수있게 만들어서 실행 횟수가 엄청 늘어났다)

그래서 이전에 이동한 위치를 visited에 저장해서 다시한번 풀어봐야겠다.

 

내가 푼 방법

 

1. 빨강구슬과 파랑구슬은 겹치면 안된다.

( 둘 다 (2,2) 지점으로 간다면 먼저 도착한 구슬(2,2) 옆에 다른 구슬이 위치한다 (2,3) )

2. 한번 실행에 파랑구슬과 빨강구슬이 같이 구멍에 들어갔다면 실패

3. 실행횟수는 10번을 넘지않는다.

4. 큐에는 빨간구슬 위치와 파란구슬 위치를 같이 저장해준다.

 

 

구슬이 구멍에 도착하면 해당 색깔 구슬 위치를 -1,-1로 지정해줬다.

( 지금 생각해보면 매우 별로인 방법이다.

후에 같은 좌표를 가지않기 위해 visited를 사용하는데 -1좌표때문에 if문을 더 써줘야한다. 아래 링크)

[백준] 13460 - 구슬 탈출2 Re (java)

 

 

 

1번을 만족시키기 위해 구슬 굴리는 순서를 정해주었다.

i는 0~3이고 순서대로 상 하 좌 우이다.

만약 (1,1) 빨간구슬과 (2,1)파란구슬을 아래로 굴린다고 생각해보자

이러면 파란색 구슬이 먼저 (3,1)에 도착하고 그 뒤(2,1)에 빨간구슬이 도착할것이다.

즉 굴리는 방향 i 에 따라 어떤구슬이 먼저 굴러가는지 정해줘야한다.

if(i==0){
    // 순서정하기
    if(temp.redR < temp.blueR) {
         data = redMove(temp , i);
         data = blueMove(data , i);
    }else{
         data = blueMove(temp , i);
         data = redMove(data , i);
    }
}else if(i==1){
    if(temp.redR < temp.blueR) {
         data = blueMove(temp , i);
         data = redMove(data , i);
    }else{
         data = redMove(temp , i);
         data = blueMove(data , i);
    }

}else if(i==2){

    if(temp.redC < temp.blueC) {
         data = redMove(temp , i);
         data = blueMove(data , i);
    }else{
         data = blueMove(temp , i);
         data = redMove(data , i);
    }

}else {

    if(temp.redC < temp.blueC) {
         data = blueMove(temp , i);
         data = redMove(data , i);
    }else{
         data = redMove(temp , i);
         data = blueMove(data , i);
    }

}

 

2번 두 구슬이 같이 구멍에 들어간다면 실패

빨간 구슬만 구멍에 들어가야지 답을 갱신해준다.

if(data.redR==-1 && data.blueR!=-1){
    if(res==-1) res = temp.count+1;
    else if(res > (temp.count+1)) res = temp.count+1;
}

 

그리고 구슬 굴리기

#을 만나면 변경하기 전 위치를 리턴하고

O를 만나면 해당 구슬 좌표를 -1로 보낸다

만약 이동하려는 위치가 다른 색 구슬 위치와 같으면 이동하기 전 위치를 보낸다.

( 1.번을 만족시키기 위해 )

private static Node redMove(Node node , int i) {
    int nr = node.redR + D[i][0];
    int nc = node.redC + D[i][1];

    if(Board[nr][nc] == '#') return node;

    if(node.blueR!=-1 && node.blueC!=-1)
        if( visited[nr][nc][node.blueR][node.blueC]) return node;

    if(Board[nr][nc] == 'O') {
        return new Node(-1,-1,node.blueR,node.blueC, node.count);
    }

    if(nr == node.blueR && nc == node.blueC) return node;

    return redMove(new Node(nr,nc,node.blueR,node.blueC, node.count),i);
}

 

 

---

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N,M;
    static char[][] Board;
    static int[][] D = {{-1,0},{1,0},{0,-1},{0,1}};
    static Queue<Node> queue = new LinkedList<>();
    static int res = -1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        Board  = new char[N+1][M+1];
        for (int i = 0; i < N; i++) {
            Board[i] = br.readLine().toCharArray();
        }
        int rRow=0,rCol=0,bRow=0,bCol=0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(Board[i][j] == 'R') {
                    Board[i][j] = '.';
                    rRow = i;
                    rCol = j;
                }
                if(Board[i][j] == 'B') {
                    Board[i][j] = '.';
                    bRow = i;
                    bCol = j;
                }
            }
        }
        queue.add(new Node(rRow,rCol,bRow,bCol,0));
        play();
    }

    private static void play() {
        int loop = 0;
        while(!queue.isEmpty()){
            Node temp = queue.remove();
            if(temp.count==10) continue;
        
            for (int i = 0; i < 4; i++) {
                // i 순서대로 상 하 좌 우
                // {{-1,0},{1,0},{0,-1},{0,1}};
                Node data;
                if(temp.redR==-1) continue;
                if(temp.blueR==-1) continue;

                if(i==0){
                    // 순서정하기
                    if(temp.redR < temp.blueR) {
                         data = redMove(temp , i);
                         data = blueMove(data , i);
                    }else{
                         data = blueMove(temp , i);
                         data = redMove(data , i);
                    }
                }else if(i==1){
                    if(temp.redR < temp.blueR) {
                         data = blueMove(temp , i);
                         data = redMove(data , i);
                    }else{
                         data = redMove(temp , i);
                         data = blueMove(data , i);
                    }

                }else if(i==2){

                    if(temp.redC < temp.blueC) {
                         data = redMove(temp , i);
                         data = blueMove(data , i);
                    }else{
                         data = blueMove(temp , i);
                         data = redMove(data , i);
                    }

                }else {

                    if(temp.redC < temp.blueC) {
                         data = blueMove(temp , i);
                         data = redMove(data , i);
                    }else{
                         data = redMove(temp , i);
                         data = blueMove(data , i);
                    }

                }
                if(data.redR==-1 && data.blueR!=-1){
                    if(res==-1) res = temp.count+1;
                    else if(res > (temp.count+1)) res = temp.count+1;
                }

                queue.add(new Node(data.redR, data.redC, data.blueR, data.blueC, temp.count + 1));

            }
        }
        System.out.println(res);
    }

    private static Node redMove(Node node , int i) {
        int nr = node.redR + D[i][0];
        int nc = node.redC + D[i][1];
        if(Board[nr][nc] == '#') return node;
        if(Board[nr][nc] == 'O') {
            return new Node(-1,-1,node.blueR,node.blueC, node.count);
        }
        if(nr == node.blueR && nc == node.blueC) return node;
        return redMove(new Node(nr,nc,node.blueR,node.blueC, node.count),i);
    }

    private static Node blueMove(Node node , int i) {
        int nr = node.blueR + D[i][0];
        int nc = node.blueC + D[i][1];
        if(Board[nr][nc] == '#') return node;
        if(Board[nr][nc] == 'O') {
            return new Node(node.redR, node.redC, -1,-1, node.count);
        }
        if(nr == node.redR && nc == node.redC) return node;
        return blueMove(new Node(node.redR, node.redC, nr,nc, node.count),i);
    }

    static class Node{
        int redR,redC;
        int blueR, blueC;
        int count;
        Node(int rr, int rc, int br, int bc, int c){
            redR = rr;
            redC = rc;
            blueR = br;
            blueC = bc;
            count = c;
        }
    }
}

 

한 번에 맞긴 했지만 시간이 어마무시하다.