developer-ellen
인간 디버거의 로그 찍기
developer-ellen
전체 방문자
오늘
어제
  • 분류 전체보기 (217)
    • 회고록 (0)
    • 취뽀 및 커리어 여정의 Stack (2)
      • SSAFY 7기 (2)
    • 프로그래밍공부 (24)
      • c++ (0)
      • JAVA (3)
      • Spring (5)
      • design pattern (3)
      • BackDB (1)
      • Servlet&JSP (3)
      • Vue (4)
      • JPA (4)
      • Infra (1)
      • Linux (0)
    • AI (3)
      • papers (3)
      • trend (0)
    • 프로젝트진행 (0)
      • 데이터베이스 (0)
      • 서버개발 (0)
      • 인공지능 (0)
      • 하루정리 (0)
    • 포트폴리오 (0)
    • 알고리즘 (158)
      • 알고리즘문풀 (155)
      • 알고리즘공부 (3)
    • 통계공부 (15)
      • 시계열분석 (15)
      • 회귀분석 (0)
    • CS (14)
      • 컴퓨터네트워크 (4)
      • 운영체제 (8)
      • 데이터베이스 (2)
    • 주저리주저리 (0)
      • 필사 (0)
    • 취업관련정보 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • ARIMA모형
  • 삼성코테기출자바풀이
  • AR모형
  • c++ 빌더 패턴
  • 통계분석
  • c++디자인패턴
  • 백준파이썬풀이
  • SW역량테스트파이썬풀이
  • 운영체제인터럽트
  • BOJ파이썬풀이
  • MA모형
  • 코테파이썬
  • 삼성코테파이썬풀이
  • 삼성코테구현풀이
  • 시계열
  • 삼성코테구현문제추천
  • 삼성코테자바풀이
  • 삼성코테기출
  • 삼성코테파이썬
  • Arima
  • SW역량테스트파이썬
  • 통계학
  • 데이터분석
  • 삼성코테자바준비
  • 카카오코테java풀이
  • 삼성코테준비
  • 삼성코테자바꿀팁
  • 삼성코테파이썬준비
  • 시계열분석
  • 카카오코테

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
developer-ellen

인간 디버거의 로그 찍기

알고리즘/알고리즘문풀

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

2021. 10. 13. 23:34

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

출처 

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

 

13460번: 구슬 탈출 2

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'

www.acmicpc.net

 

 

📝 문제해결법

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};
	}
	
	 

}

 

'알고리즘 > 알고리즘문풀' 카테고리의 다른 글

BOJ - 주사위 굴리기 14499번 (python)  (0) 2021.10.14
BOJ - 뱀 3190번 (python)  (0) 2021.10.14
BOJ - 공주님을 구해라! 17839번 (python)  (0) 2021.10.13
BOJ - 숨바꼭질3 13549번 (python)  (0) 2021.10.07
BOJ - 치즈 2636번 (python)  (0) 2021.10.06
    '알고리즘/알고리즘문풀' 카테고리의 다른 글
    • BOJ - 주사위 굴리기 14499번 (python)
    • BOJ - 뱀 3190번 (python)
    • BOJ - 공주님을 구해라! 17839번 (python)
    • BOJ - 숨바꼭질3 13549번 (python)
    developer-ellen
    developer-ellen

    티스토리툴바