BOJ - 구슬 탈출 2 13460번 (python/JAVA)

❓ 문제 - 백준 구슬 탈출 2 13460번 - python 풀이법

출처 

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

13460번: 구슬 탈출 2

 

 

📝 문제해결법

1. 이 문제는 그래프탐색(BFS) + 구현으로 풀었다.

• bfs를 통해 4방향으로 기울리면서 구슬을 움직이는데, 기울린 횟수(depth)가 10회가 넘는다면 실패이므로 break를 통해 -1를 리턴한다.
• 4방향으로 기울리는 것은 move 함수를 통해 기울림을 구현하고, 한 방향으로 계속 움직이다가 만약 벽이 마주치거나 원래 위치가 구멍이라면 움직이는 것을 종료한 후 움직인 후의 위치와 움직인 횟수를 리턴한다.
• move 함수를 통해 4방향으로 기울려서 만약 기울린 후 파란 구슬의 위치가 구멍이 아니면서 빨간 구슬의 위치가 구멍이라면 기울린 횟수(depth)를 리턴하여 출력한다.
• 만약 기울린 후 파란 구슬의 위치가 구멍이 아니고, 파란 구슬과 빨간 구슬의 위치가 같으면 move 함수를 통해 리턴받은 한 방향으로 움직인 횟수를 비교해서 만약 빨간 구슬이 더 움직였다면 파란 구슬 뒤로 이동하고, 파란 구슬이 더 움직였다면 빨간 구슬 뒤로 이동시켜준다.
• 빨간구슬과 파란구슬의 기울여서 이동한 위치를 visited 4차원 리스트를 통해 방문처리 해주는데, 만약 방문 처리 되지 않은 곳 (기울여서 이동한 곳이 처음인 곳)이라면 queue에 현재 빨간 구슬과 파란 구슬의 위치와 depth+1해줘서 queue에 append 한다.
• visited 4차원 리스트로 구현해도 되는 것은 n, m 정수 범위가 3 이상 10이하 이므로 메모리 제한 512MB에 걸리지 않기 때문이다.

2. 메인코드

• graph 정보를 입력받으면서 빨간 구슬과 파란 구슬의 위치를 저장하여 bfs를 호출하여 기울린 횟수 또는 -1(실패)를 반환받아 출력한다.

 

 

💻 소스코드 (python)

# 구슬탈출 2 - BOJ 13460
# BFS + 구현
from collections import deque

n, m = map(int, input().split())
graph = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
rx, ry, bx, by = 0, 0, 0, 0
visited = [[[[False] * m for _ in range(n)] for _ in range(m)] for _ in range(n)]

for i in range(n):
    data = list(input())
    graph.append(data)
    for d in range(len(data)):
        if data[d] == 'R':
            rx, ry = i, d
        elif data[d] == 'B':
            bx, by = i, d

def move(x, y, dx, dy):
    count = 0
    while graph[x+dx][y+dy] != '#' and graph[x][y] != 'O':
        x += dx
        y += dy
        count += 1
    return x, y, count

def bfs(rx, ry, bx, by):
    q = deque()
    q.append((rx, ry, bx, by, 1))
    visited[rx][ry][bx][by] = True
    while q:
        r_x, r_y, b_x, b_y, depth = q.popleft()
        if depth > 10:
            break
        for i in range(4):
            r_nx, r_ny, r_cnt = move(r_x, r_y, dx[i], dy[i])
            b_nx, b_ny, b_cnt = move(b_x, b_y, dx[i], dy[i])
            if graph[b_nx][b_ny] != 'O':
                if graph[r_nx][r_ny] == 'O':
                    return depth
                if r_nx == b_nx and r_ny == b_ny:
                    if r_cnt > b_cnt:
                        r_nx -= dx[i]
                        r_ny -= dy[i]
                    else:
                        b_nx -= dx[i]
                        b_ny -= dy[i]
                if not visited[r_nx][r_ny][b_nx][b_ny]:
                    visited[r_nx][r_ny][b_nx][b_ny] = True
                    q.append((r_nx, r_ny, b_nx, b_ny, depth+1))
    return -1


print(bfs(rx, ry, bx, by))

 

💻 소스코드 (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;


public class Main_13460 {
	public static int n, m;
	public static char[][] map;
	
	
	// 위, 아래, 왼, 오
	public static int[] dx = {-1, 1, 0, 0};
	public static int[] dy = {0, 0, -1, 1};
	public static boolean[][][][] visited;
	public static class Data {
		int r_x;
		int r_y;
		int b_x;
		int b_y;
		int cnt;
		public Data(int r_x, int r_y, int b_x, int b_y, int cnt) {
			this.r_x = r_x;
			this.r_y = r_y;
			this.b_x = b_x;
			this.b_y = b_y;
			this.cnt = cnt;
		}
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] data = br.readLine().split(" ");
		n = Integer.parseInt(data[0]);
		m = Integer.parseInt(data[1]);
		
		map = new char[n][m];
		int b_x = 0, b_y = 0, r_x = 0, r_y = 0;
		for(int i=0;i<n;i++) {
			map[i] = br.readLine().toCharArray();
			for(int j=0;j<m;j++) {
				if(map[i][j] == 'B') {
					b_x = i;
					b_y = j;
				} else if(map[i][j] == 'R') {
					r_x = i;
					r_y = j;
				}
			}
		}
		
		int ans = bfs(b_x, b_y, r_x, r_y);
		
		System.out.println(ans);
		

	}
	
	public static int bfs(int b_x, int b_y, int r_x, int r_y) {
		visited = new boolean[n][m][n][m];
		visited[r_x][r_y][b_x][b_y] = true;
		Queue<Data> q = new LinkedList<>();
		q.offer(new Data(r_x, r_y, b_x, b_y, 0));
		
		
		while (!q.isEmpty()) {
			Data data = q.poll();
			if(data.cnt >= 10) {
				return -1;
			}
			
			for(int d=0;d<4;d++) {
            	// 해당 방향으로 빨간구슬, 파란구슬 이동
				int[] moving = move(data.r_x, data.r_y, data.b_x, data.b_y, d);
				int rx = moving[0];
				int ry = moving[1];
				int bx = moving[2];
				int by = moving[3];
				int rcnt = moving[4];
				int bcnt = moving[5];
	
				if(map[bx][by] != 'O') {
                	// 이동한 곳에 빨간 구슬만 구멍에 빠졌다면 이동한 횟수 리턴
					if(map[rx][ry] == 'O') {
						return data.cnt+1;
					} 
					
                    // 이동했을 때 빨간구슬 = 파란구슬의 위치로 겹치는 경우
                    // 만약 빨간 구슬이 더 움직임? 그럼 파란 구슬 뒤로 보내기
                    // 만약 파란 구슬이 더 움직임? 그럼 빨간 구슬 뒤로 보내기
					if(rx == bx && ry == by) {
						if(rcnt > bcnt) {
							rx -= dx[d];
							ry -= dy[d];
						} else {
							bx -= dx[d];
							by -= dy[d];
						}
					}
                    
                    // 이동한 해동 위치가 방문한 적이 없으면 큐에 넣고 BFS 돌도록 구현
					if(!visited[rx][ry][bx][by]) {
						q.offer(new Data(rx, ry, bx, by, data.cnt+1));
						visited[rx][ry][bx][by] = true;
					}
				} 
			}
			
		}
		
		
		
		return -1;
	}
	
	public static int[] move(int r_x, int r_y, int b_x, int b_y, int d) {
		int r_cnt = 0;
		
		while (true) {			
			r_x += dx[d];
			r_y += dy[d];
			if(map[r_x][r_y] == '#') {
				r_x -= dx[d];
				r_y -= dy[d];
				break;
				
			}
			r_cnt++;
			if(map[r_x][r_y] == 'O') {
				break;
			}
		}
		
		int b_cnt = 0;
		while(true) {
			b_x += dx[d];
			b_y += dy[d];
			if(map[b_x][b_y] == '#') {
				b_x -= dx[d];
				b_y -= dy[d];
				break;
				
			} 
			b_cnt++;
			if(map[b_x][b_y] == 'O') {
				break;
			}
		}
		
		return new int[]{r_x, r_y, b_x, b_y, r_cnt, b_cnt};
	}
	
	 

}