B12460. 구슬탈출2

13460번: 구슬 탈출 2

13460번: 구슬 탈출 2

 

 

최단거리⇒bfs(⇒Queue)

1. Queue에 원소가 없다면 종료
2. Queue의 원소가 있다면?
   1. 종료조건 확인
   2. 꺼내서 구슬을 움직임(구현)
   3. 큐에 다음 수행 추가

 

python

from collections import deque

N,M=map(int, input().split(" "))
board=[]
for i in range(N):
    board.append([])
    string = input()
    for s in string:
        board[i].append(s)
Q=deque([]) #[rx,ry,bx,by,index,cnt]

def bfs():
    global Q, board, N, M, result
    
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]

    while(len(Q)!=0):
        cur = Q.popleft()
        rx,ry,bx,by,index,cnt = cur[0],cur[1],cur[2],cur[3],cur[4],cur[5]
        #종료조건을 만족하는지 검사
        #10번이상 수행되었다면 종료
        if(cnt>=11):
            continue
        #파란색 구슬이 구멍에 들어갔다면 무조건 종료
        if(board[bx][by]=="O"):
            continue
        #빨간 구슬만 구멍에 들어갔다면 종료
        if(board[rx][ry]=="O"):
            return cnt

        #구현
        nrx,nry,nbx,nby=rx,ry,bx,by
        while True: #빨간구슬            
            nrx+=dx[index]
            nry+=dy[index]
            if(board[nrx][nry]=="O"): #구멍을 만나면
                break
            if(board[nrx][nry]=="#"): #벽을 만나면
                nrx-=dx[index]
                nry-=dy[index]
                break
            
        while True: #파란구슬
            nbx+=dx[index]
            nby+=dy[index]
            if(board[nbx][nby]=="O"): #구멍을 만나면
                break
            if(board[nbx][nby]=="#"): #벽을 만나면
                nbx-=dx[index]
                nby-=dy[index]
                break
            
        #빨간구슬과 파란구슬이 같은 위치에 있을 때 위치 조정
        if(board[nrx][nry]!="O" and nrx==nbx and nry==nby):
            if(index==0):
                nrx = nrx+1 if rx>bx else nrx
                nbx = nbx+1 if bx>rx else nbx
            if(index==1):
                nrx = nrx-1 if rx<bx else nrx
                nbx = nbx-1 if bx<rx else nbx
            if(index==2):
                nry = nry+1 if ry>by else nry
                nby = nby+1 if by>ry else nby
            if(index==3):
                nry = nry-1 if ry<by else nry
                nby = nby-1 if by<ry else nby

        for i in range(4):
            if(index!=i):
                Q.append([nrx,nry,nbx,nby,i,cnt+1])

    return -1

#초기 rx,ry,bx,by 위치 구하기
rx,ry,bx,by=-1,-1,-1,-1
for i in range(N):
    for j in range(M):
        if(board[i][j]=="R"):
           rx,ry=i,j
        if(board[i][j]=="B"):
           bx,by=i,j

for i in range(4):
    Q.append([rx,ry,bx,by,i,0])

result=bfs()
print(result)

 

java

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static class Marble {
        int rx;
        int ry;
        int bx;
        int by;
        int index;
        int cnt;

        Marble(int rx, int ry, int bx, int by, int index, int cnt) {
            this.rx = rx;
            this.ry = ry;
            this.bx = bx;
            this.by = by;
            this.index = index;
            this.cnt = cnt;
        }
    }

    public static String[][] board;
    public static int N;
    public static int M;
    public static Queue<Marble> Q = new LinkedList<>();
    static boolean[][][][] visited;
    public static int[] dx = {-1,1,0,0}; //UP, DOWN, LEFT, RIGHT
    public static int[] dy = {0,0,-1,1};

    public static int bfs() {
        if (Q.isEmpty()) {
            //1. 큐가 비어있다면: 더 이상 움직일 수 없는 상태
            return -1;
        }

        //2 .큐가 비어있지 않다면
        while (!Q.isEmpty()) {
            Marble marble = Q.poll();
            int index = marble.index;
            int rx = marble.rx;
            int ry = marble.ry;
            int bx = marble.bx;
            int by = marble.by;
            int cnt = marble.cnt;
            int startRx = rx;
            int startRy = ry;
            int startBx = bx;
            int startBy = by;

            //2-1. index 방향으로 구슬을 이동시킴
            while(true){
                //구멍에 들어가면 종료
                if(board[rx][ry].equals("O")){
                    break;
                }
                //범위 이내면 전진
                if(rx+dx[index]>=0 && rx+dx[index]<=N-1 && ry + dy[index]>=0 && ry + dy[index]<=M-1 && !board[rx+dx[index]][ry+dy[index]].equals("#")){
                    rx = rx + dx[index];
                    ry = ry + dy[index];
                }else{
                    break;
                }
            }
            while(true){
                //구멍에 들어가면 종료
                if(board[bx][by].equals("O")){
                    break;
                }
                //범위 이내면 전진
                if(bx+dx[index]>=0 && bx+dx[index]<=N-1 && by + dy[index]>=0 && by + dy[index]<=M-1 && !board[bx+dx[index]][by+dy[index]].equals("#")){
                    bx = bx + dx[index];
                    by = by + dy[index];
                }else{
                    break;
                }
            }

            //빨간구슬과 파란구슬의 위치가 충돌한 경우 위치조정
            // 둘 다 구멍에 빠지지 않았는데 이동할 위치가 같은 경우 -> 위치 조정
            if(rx == bx && ry == by && !board[rx][ry].equals("O") && !board[bx][by].equals("O")) {
                if(index == 0) {
                    //UP
                    if(startRx > startBx) rx -= dx[index];
                    else bx -= dx[index];
                } else if(index == 1) {
                    // DOWN
                    if(startRx < startBx) rx -= dx[index];
                    else bx -= dx[index];
                } else if(index == 2) {
                    //LEFT
                    if(startRy > startBy) ry -= dy[index];
                    else by -= dy[index];
                } else {
                    //RIGHT
                    if(startRy < startBy) ry -= dy[index];
                    else by -= dy[index];
                }
            }

            //2-2. 종료 조건을 만족하는지 확인
            //2-2-2. cnt의 limit을 초과한 경우 → return -1
            if (cnt > 10) {
                continue;
            }
            if(board[bx][by].equals("O")){
                //2-1-2. 파란 구슬이 구멍에 들어간 경우(무조건 실패) → return -1
                continue;
            }else if(!board[bx][by].equals("O") && board[rx][ry].equals("O")){
                //2-1-3. 빨간 구슬만 구멍에 들어간 경우 → return cnt
                return cnt;
            }

            //2-3. 종료 조건을 만족하지 않으므로 가능한 경우를 다시 큐에 넣음
            //board의 끝이거나 주변이 벽이면 더 이상 움직일 수 없음
            //진행방향에 구슬이 있다면 더이상 움직일 수 움직일 수 없음
            if((rx>0 && !board[rx-1][ry].equals("#") && !(rx-1==bx && ry==by)) || (bx>0 && !board[bx-1][by].equals("#") && !(bx-1==rx && by==ry) )){
                //UP 방향으로 더 움직일 수 있는가?
                if(!visited[rx][ry][bx][by]){
                    Q.offer(new Marble(rx, ry, bx, by,0, cnt+1));
                }
            }
            if((rx<N-1 && !board[rx+1][ry].equals("#") && !(rx+1==bx && ry==by) ) || (bx<N-1 && !board[bx+1][by].equals("#") && !(bx+1==rx && by==ry))){
                //DOWN 방향으로 더 움직일 수 있는가?
                if(!visited[rx][ry][bx][by]){
                    Q.offer(new Marble(rx, ry, bx, by,1, cnt+1));
                }
            }
            if((ry>0 && !board[rx][ry-1].equals("#") && !(rx==bx && ry-1==by) ) || (by>0 && !board[bx][by-1].equals("#") && !(bx==rx && by-1==ry) )){
                //Left 방향으로 더 움직일 수 있는가?
                if(!visited[rx][ry][bx][by]){
                    Q.offer(new Marble(rx, ry, bx, by,2, cnt+1));
                }
            }
            if((ry<M-1 && !board[rx][ry+1].equals("#") && !(rx==bx && ry+1==by) ) || (by<M-1 && !board[bx][by+1].equals("#") && !(bx==rx && by+1==ry) )){
                //Right 방향으로 더 움직일 수 있는가?
                if(!visited[rx][ry][bx][by]){
                    Q.offer(new Marble(rx, ry, bx, by,3, cnt+1));
                }
            }
            visited[rx][ry][bx][by] = true;
        }

        return -1;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        sc.nextLine();
        board = new String[N][M];
        visited = new boolean[N][M][N][M];
        for(int i=0;i<N;i++){
            board[i] = sc.nextLine().split("");
        }

        int rx=-1,ry=-1,bx=-1,by=-1;
        for(int i=0;i<N;i++) {
            for(int j=0;j<M;j++) {
                if(board[i][j].equals("R")) {
                    rx=i;
                    ry=j;
                }
                if(board[i][j].equals("B")) {
                    bx=i;
                    by=j;
                }
            }
        }

        visited[rx][ry][bx][by]=true;
        if((rx>0 && !board[rx-1][ry].equals("#") && !(rx-1==bx && ry==by)) || (bx>0 && !board[bx-1][by].equals("#") && !(bx-1==rx && by==ry))){
            Q.offer(new Marble(rx, ry, bx, by,0, 1));
        }
        if((rx<N-1 && !board[rx+1][ry].equals("#") && !(rx+1==bx && ry==by)) || (bx<N-1 && !board[bx+1][by].equals("#") && !(bx+1==rx && by==ry))){
            Q.offer(new Marble(rx, ry, bx, by,1, 1));
        }
        if((ry>0 && !board[rx][ry-1].equals("#") && !(rx==bx && ry-1==by)) || (by>0 && !board[bx][by-1].equals("#") && !(bx==rx && by-1==ry))){
            Q.offer(new Marble(rx, ry, bx, by,2, 1));
        }
        if((ry<M-1 && !board[rx][ry+1].equals("#") && !(rx==bx && ry+1==by )) || (by<M-1 && !board[bx][by+1].equals("#") && !(bx==rx && by+1==ry))){
            Q.offer(new Marble(rx, ry, bx, by,3, 1));
        }

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