[백준_13460]구슬 탈출 2 with Python, Java

백준(BOJ) "삼성 SW 역량 테스트 기출 문제" 문제집: 구슬 탈출 2(골드 2)

문제 출처:www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

 

1.알고리즘

고려할만한 사항들은 유의 사항에 적어놨다.

Python으로 풀었다가...최근에 Java로 또 풀었다... 사실 처음에 문제보고 엥 이걸 내가 어케 품;; 하고 당황하고 있다가.... 4차원 배열 얘기를 했던 이 게시글이 생각나서 설마 이건가??하고 풀었음. ㅎㅎ < 정리의 중요성...

Java코드의 경우, 로직은 동일하기 때문에 조금 달라진 부분에 대해서만 주석 설명함.

• 입력 값 입력받을 때, 빨간 구슬(R), 파란 구슬(B)의 좌표를 별도로 받아둔 후 보드의 구슬을 제거
• BFS 알고리즘을 활용한 find_ball_move_direction 함수로 구슬 이동
  • route에 현재 구슬 위치 데이터(Rx, Ry, Bx, By, 구슬 이동횟수=move_count)
  • move_count > 10 이면 break로 반복문 종료
  • 4 방향(상, 하, 좌, 우)으로 구슬을 이동, move_ball 함수 사용.
• move_ball 함수로 구슬 이동
  • 구슬이 한 칸 이동한 후(nx, ny)의 board를 확인, 갈 수 있는 경로이면 이동
  • 현재 이동한 곳이 'O' 탈출구이면 이동한 좌표, 이동 거리 반환
  • 탈출구가 아니면 한 칸 이동 전의 데이터, 이동 거리 반환
    • 초기 nx, ny 값이 이미 한 칸 이동한 데이터이기 때문에 nx-dx[d], ny-dy[d] 값 반환
• find_ball_move_direction 함수
  • 반환받은 B구슬의 좌표를 확인, 'O' 탈출구이면 다음 방향으로 전환
  • B구슬 좌표가 'O' 탈출구가 아니고, R구슬 좌표가 'O' 탈출구이면 탈출. move_count 반환
  • B구슬, R구슬 좌표가 모두 'O' 탈출구가 아니면 구슬 좌표 확인, 다음 경로로 route 추가
    • B구슬과 R구슬의 좌표가 같으면 각 구슬의 이동 거리를 확인.
      • R구슬의 이동거리가 B구슬의 이동거리보다 길면, R구슬을 한 칸 뒤로
      • R구슬의 이동거리가 B구슬의 이동거리보다 짧으면, B구슬을 한 칸 뒤로
    • 방문했던 위치인지 확인
      • 방문하지 않은 경우, 방문 여부를 True로 설정
      • route에 경로(nrx, nry, nbx, nby, 이동 횟수 + 1) 추가
  • 모든 경로 탐색이 끝났거나, break 문으로 반복문이 종료된 경우, -1 반환
• find_ball_move_direction 함수 결과 값 result 출력

 

2. 유의 사항

• R, B구슬을 board에서 옮겨줄 것이 아니라면, board데이터에서 삭제 필요.
  • 삭제 하지 않을 경우, 각 구슬이 존재하지 않는 R, B구슬에 막혀 이동 불가능
• 4개의 좌표(R구슬 x좌표, R구슬 y좌표, B구슬 x좌표, B구슬 y좌표)를 확인해줘야 하기 때문에 4차원 배열 사용
  • R구슬과 B구슬 각각은 방문한 곳에 재방문이 가능 ▶ NxM행렬 두 개로 방문 확인 X
  • 하지만 두 구슬이 동시에 같은 곳을 방문하는 것은 제자리돌기 ▶ 두 구슬의 좌표 동시 확인 필요
• 구슬 이동 횟수는 이전 위치까지의 이동 횟수에 따라 다를 수 있음 = 한 번에 이동하는 것이 아님
  • (3, 3)까지의 이동 횟수가 2번이나 3번이 될 수 있음 = 오직 한 가지의 경우를 가지지 않음
  • 각 위치까지의 이동 횟수를 세어주어야함

 

3. 어려웠던 점, 해결 방법

• move_ball 함수의 좌표 확인을 잘못했음. 현재 구슬이 있는 위치의 좌표를 확인하고, 좌표를 옮겨줬음
  • 구슬이 이동할 위치의 좌표를 확인하고, 좌표를 옮겨줬음
• 이동 횟수를 잘못 세어줬음.
  • route에 이동횟수를 함께 포함. 이동할 때 몇 번 이동했는 지 함께 기록하여 다뤄줌.

 

4. 소스 코드

상세 코드 설명은 주석

4-1. Python

import sys
from collections import deque
 
#구슬 이동
def move_ball(x, y, d):
    #구슬이 이동할 좌표
    nx, ny = x+dx[d], y+dy[d]
    move_distance = 0
    #이동할 좌표를 확인, 이동할 수 있는 만큼 이동
    while board[nx][ny] == '.':
        nx += dx[d]
        ny += dy[d]
        move_distance += 1
    #이동한 곳이 탈출구이면 현재 좌표, 이동 거리 반환
    if board[nx][ny] == 'O':
        return nx, ny, move_distance
    #이동한 곳이 탈출구가 아니면, 이동 전의 좌표, 이동 거리 반환
    else:
        return nx-dx[d], ny-dy[d], move_distance
 
#BFS로 구슬 이동
def find_ball_move_direction(rx, ry, bx, by):
    #빨간 구슬 x, 빨간 구슬 y, 파란 구슬 x, 파란 구슬 y, 이동 횟수
    route = deque([(rx, ry, bx, by, 1)])
    visited[rx][ry][bx][by] = True
 
    while route:
        rx, ry, bx, by, move_count = route.popleft()
 
        #이동 횟수가 10번을 초과하면 반복문 종료
        if move_count > 10:
            break
 
        for idx in range(4):
            nrx, nry, r_distance = move_ball(rx, ry, idx)
            nbx, nby, b_distance = move_ball(bx, by, idx)
 
            #파란 구슬이 탈출구에 도착했는 지 확인
            if board[nbx][nby] == 'O':
                continue
            #파란 구슬이 도착하지 않고, 빨간 구슬이 도착했는지 확인
            elif board[nrx][nry] == 'O':
                return move_count
            #두 구슬이 모두 도착하지 않았을 때
            else:
                #두 구슬이 같은 칸에 있을 때
                if (nrx, nry) == (nbx, nby):
                    if r_distance > b_distance:
                        nrx -= dx[idx]
                        nry -= dy[idx]
                    else:
                        nbx -= dx[idx]
                        nby -= dy[idx]
 
                #빨간 구슬, 파란 구슬이 동시에 같은 곳에 방문했는지 확인
                if not visited[nrx][nry][nbx][nby]:
                    visited[nrx][nry][nbx][nby] = True
                    route.append((nrx, nry, nbx, nby, move_count + 1))
 
    return -1
 
 
if __name__ == '__main__':
    N, M = map(int, sys.stdin.readline().split())
    #board 입력. 빨간 구슬, 파란 구슬 좌표 기억, 보드에서 제거.
    board = []
    for r in range(N):
        board_line = str(*map(str, sys.stdin.readline().split()))
        for c in range(M):
            if board_line[c] == 'R':
                r_r, r_c = r, c
                board_line = board_line.replace('R', '.')
            elif board_line[c] == 'B':
                b_r, b_c = r, c
                board_line = board_line.replace('B', '.')
        board.append(board_line)
 
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    #빨간 구슬, 파란 구슬 좌표 확인을 위한 4차원 배열
    visited = [[[[False]*M for _ in range(N)] for _ in range(M)] for _ in range(N)]
    result = find_ball_move_direction(r_r, r_c, b_r, b_c)
    print(result)

 

 

4-2. Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
 
public class Main {
    
    static int N, M;
    static char[][] board;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static class Node{    //공 정보를 담을 Node 클래스
        int rx;        //빨간 공 행
        int ry;        //빨간 공 열
        int bx;        //파란 공 행
        int by;        //파란 공 열
        int moveCnt;//움직인 횟수
        Node(int rx, int ry, int bx, int by, int moveCnt) {    
            super();
            this.rx = rx;
            this.ry = ry;
            this.bx = bx;
            this.by = by;
            this.moveCnt = moveCnt;
        }
    }
    
    public static void main(String[] args) throws Exception{
        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][M];
        int rx = -1, ry = -1, bx = -1, by = -1;
        for(int r=0; r<N; r++) {
            board[r] = br.readLine().toCharArray();
            for(int c=0; c<M; c++) {
                if(board[r][c] == 'R') {
                    board[r][c] = '.';
                    rx = r;
                    ry = c;
                }else if(board[r][c] == 'B') {
                    board[r][c] = '.';
                    bx = r;
                    by = c;
                }
            }
        }
        
        int result = moveBall(rx, ry, bx, by);
        System.out.println(result);
    }
    
    
    private static int moveBall(int rx, int ry, int bx, int by) {
        Queue<Node> route = new LinkedList<>();
        boolean[][][][] visited = new boolean[N][M][N][M];
        route.add(new Node(rx, ry, bx, by, 1));
        visited[rx][ry][bx][by] = true;
        
        while(!route.isEmpty()) {
            Node node = route.poll();
            
            if(node.moveCnt > 10) return -1;
            for(int i=0; i<4; i++) {
                Node nr = findBallDirection(node.rx, node.ry, i, true);        //4번째 인자는 빨간 공인지 파란 공인지 전달
                Node nb = findBallDirection(node.bx, node.by, i, false);
                
                if(board[nb.bx][nb.by] == 'O') continue;
                else if(board[nr.rx][nr.ry] == 'O') return node.moveCnt;
                else {
                    if(nr.rx == nb.bx && nr.ry == nb.by) {
                        if(nr.moveCnt < nb.moveCnt) {
                            nb.bx -= dx[i];
                            nb.by -= dy[i];
                        }else {
                            nr.rx -= dx[i];
                            nr.ry -= dy[i];
                        }
                    }
                    
                    if(visited[nr.rx][nr.ry][nb.bx][nb.by]) continue;
                    visited[nr.rx][nr.ry][nb.bx][nb.by] = true;
                    route.add(new Node(nr.rx, nr.ry, nb.bx, nb.by, node.moveCnt+1));
                }
            }
        }
 
        return -1;
    }
    
    
    private static Node findBallDirection(int x, int y, int dirc, boolean isRed) {
        int cnt = 1;
        int nx = x+dx[dirc];
        int ny = y+dy[dirc];
        while(board[nx][ny] == '.') {
            nx+=dx[dirc];
            ny+=dy[dirc];
            cnt++;
        }
        
        if(board[nx][ny] != 'O') {
            nx-=dx[dirc];
            ny-=dy[dirc];
        }
        if(isRed) return new Node(nx, ny, -1, -1, cnt);
        return new Node(-1, -1, nx, ny, cnt);
    }
}

 

5. 고민

• 솔직히 말하면 Python보다 Java 코드가 더 빠를 것같다고 생각했는데....오히려 조금이지만 더 걸렸다. 일단 메모리 사용량이 절반 이하로 줄어서 그건 인상깊다 흠...