[Algorithm] SW 기출문제 - 구슬 탈출2 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

이번 포스팅은 SW 기출문제인 구슬 탈출2 문제를 해결하는 과정을 정리하도록 하겠습니다.

 

문제 출처: 

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

13460번: 구슬 탈출 2

 

 

1. 풀이 소스 

 

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());
        
        Board board = new Board(n, m);
        
        for (int i = 0; i < n; i++) board.setMap(br.readLine(), i);
        board.moveMarble();
        System.out.println(board.getAnswer());
    }
}

class Board {
    
    static final int[] DX = {-1, 0, 1, 0};
    static final int[] DY = {0, -1, 0, 1};
    
    int n, m;
    Marble redMarble, blueMarble;
    char[][] map;
    boolean[][][][] visited; // Red, Blue 구슬의 각 각 x, y의 방문 여부
    int answer = -1;
    
    Board(int n, int m) {
        this.n = n;
        this.m = m;
        map = new char[n][m];
        visited = new boolean[n][m][n][m];
    }
    
    void setMap(String str, int idx) {
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            map[idx][i] = ch;
            
            if (ch == 'R') redMarble = new Marble(idx, i, 0);
            else if (ch == 'B') blueMarble = new Marble(idx, i, 0);
        }
    }
    
    void moveMarble() {

        Queue<Marble> redQ = new ArrayDeque<>();
        Queue<Marble> blueQ = new ArrayDeque<>();
        
        redQ.add(redMarble);
        blueQ.add(blueMarble);
        
        while(!redQ.isEmpty() && !blueQ.isEmpty()) {
            Marble red = redQ.poll();
            Marble blue = blueQ.poll();

            if (red.step > 10) { // bfs 원리로 인해 x 위치에서 -1, +1 등을 수행하더라도 각 움직인 위치는 step + 1
                answer = -1;
                return;
            }
            
            // 파란색이 0에 도착한 경우
            if (map[blue.x][blue.y] == 'O') continue; // 다른 방법이 존재할 수 있으므로 해당 경로로 진행하는 것만 중지
            
            // 파란색이 도착하지 않고 빨간색이 O에 도착한 경우
            if (map[red.x][red.y] == 'O') {
                answer = red.step;
                return;
            }    
            
            for (int i = 0; i < 4; i++) {
                int bx = blue.x; // 반드시 blue부터 실행
                int by = blue.y; 

                boolean isBlueCheck = false; // 파란 구슬이 'O'에 들어가는지 체크

                while (true) {
                    bx += DX[i];
                    by += DY[i];
                    
                    if (map[bx][by] == 'O') {
                        isBlueCheck = true;
                        break;
                    }
                    
                    else if (map[bx][by] == '#') {
                        bx -= DX[i];
                        by -= DY[i];
                        break;
                    }
                }

                if (isBlueCheck) continue; // 만약 'O'에 파란 구슬이 도착하는 경우 선행 조건과 관계없이 queue에 넣지 않음
                
                int rx = red.x;
                int ry = red.y;
                
                while(true) {
                    rx += DX[i];
                    ry += DY[i];
                    
                    if (map[rx][ry] == 'O') break;
                    else if (map[rx][ry] == '#') {
                        rx -= DX[i];
                        ry -= DY[i];
                        break;
                    }
                }
                
                // 두개의 위치가 같다면 
                // 서로 다른 큐에 의해 구슬의 앞 뒤 관계를 고려하지 않고 이동하였으므로
                // 두 구슬의 우선순위에 따라 배치를 다르게 해야 함
                if (bx == rx && by == ry && map[rx][ry] != 'O') {
                    
                    // 맨해튼 거리 공식을 쓰는 이유 -> x, y 가 한칸씩 움직일 수 있으므로
                    int redDist = Math.abs(red.x - rx) + Math.abs(red.y - ry);
                    int blueDist = Math.abs(blue.x - bx) + Math.abs(blue.y - by);
                    
                    if (redDist > blueDist) {
                        rx -= DX[i];
                        ry -= DY[i];
                    } else {
                        bx -= DX[i];
                        by -= DY[i];
                    }
                }
                
                if (!visited[rx][ry][bx][by]) {
                    visited[rx][ry][bx][by] = true;
                    
                    redQ.add(new Marble(rx, ry, red.step + 1));
                    blueQ.add(new Marble(bx, by, blue.step + 1));
                }
            }
        }
    }
    
    int getAnswer() {
        return this.answer;
    }
    
    class Marble {
        int x;
        int y;
        int step;
        
        Marble(int x, int y, int step) {
            this.x = x;
            this.y = y;
            this.step = step;
        }
    }
}

 

 

2. 풀이 과정

 

해당 문제는 해결하지 못하여 하단의 블로그를 참고하였습니다. 

풀이 중점 사항은 다음과 같습니다.

 

빨간 구슬, 파란 구슬을 저장할 Queue를 각각 선언합니다.

빨간 구슬, 파란 구슬이 움직일 때, 상하좌우 인접한 곳에 구슬이 있다면 이동에 제약이 생길 수 있습니다.

이를 모두 한 번에 고려하게 된다면 복잡해지기 때문에, 하나의 통일된 조건으로 묶어서 판단할 수 있습니다.

• 상하좌우로 각 구슬을 각 각 이동시킵니다.
• 예를 들어 위로 구슬을 이동시킬 경우, 빨강, 파랑 구슬은 동시에 위로 올라가게 됩니다.
• 위치한 곳이 서로 다르다면, 겹치는 경로로 움직이지 않았음을 의미합니다.
• 만약 이동한 곳이 동일하다면, 두 구슬은 인접한 곳에서 겹치는 경로로 이동하였음을 의미합니다.
• 겹치는 경로로 이동한 경우 어떤 구슬이 앞 서 있었는지 판단하기 위해 맨해튼 거리 공식을 활용하여 최초 출발한 위치에서 도착한 위치를 빼서 더 먼 구슬은 도착한 위치 -1을 합니다.
• 이동하는 순서는 반드시 파란 구슬부터 진행하여, 만약에 파란 구슬이 이동하는 시점에 'O'를 마주한다면 queue에 넣지 않고 continue 합니다.
• 한 번 설정한 좌표를 토대로 while문으로 장애물 혹은 'O'을 만날 때까지 반복하는 과정에서 파란 구슬은 빨간 구슬의 선행 조건에 상관없이 'O'에 도착한다면 종료합니다.
• 그 이유는 'O'에 빨간 구슬이 도착하든 혹은 파란 구슬이 먼저 도착하든 구슬은 빠져나가게 되어있습니다. 따라서, 빨간 구슬이 선행되어 있더라도 파란 구슬이 이어서 'O'에 오게 되므로 종료시킵니다.
• 반면, 빨간 구슬이 'O'에 도착한 경우 바로 return 하지 않는 이유는 queue에 넣는 조건이 red.step > 10이므로 큐에서 나와 들어갔을 때는, step이 10일 수도 있습니다. 따라서, step + 1인 경우 11이므로 -1을 리턴해야 할 수 있습니다.
• 해당 조건 코드는 queue에서 나올 때 검증하므로 while문에는 작성하지 않았습니다.

 

중요한 포인트는, bfs를 구현하기 위해 방문 위치를 4차원 배열로 설정하여 방문한 곳에 동일하게 방문하는 것을 방지해야합니다. 나아가, 두 큐를 분리하였기 때문에 두 구슬이 동일한 위치에 도착한다면 선행 조건을 파악하기 위해 맨해튼 거리 공식을 적용해야 했습니다.

 

많이 어려웠던 문제였고 해이해진 정신을 바로잡을 수 있는 기회였습니다.

이상으로 SW 기출문제 구슬 탈출2 문제 풀이를 마치겠습니다. 감사합니다.!!!

 

 

참고 블로그: https://wellbell.tistory.com/44