220821 - 돌 던지기

이상해씨·2022년 8월 21일

알고리즘 풀이

목록 보기

92/94

◾ 돌 던지기 : 백준 3025번 (플래티넘 4)

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

문제

이 모든 사건의 시작은 2주 전이었다. 그 날 상근이는 복도에 누워서 잠을 자고 있었다. 커다란 돌을 들고 그 옆을 지나가던 민혁이는 복도에서 잠을 자는 사람을 처음봐서 신기하게 쳐다보고 있었다. 그 때였다. 들고 있던 돌을 상근이의 왼 발에 떨어뜨렸다. 상근이는 응급실로 실려갔고, 한 달 동안 침대에 누워서 휴식을 취해야 한다는 진단을 받았다. 민혁이는 미안한 마음에 하던 일을 모두 중단하고 상근이를 간호하기로 했다.

상근이는 2주 동안 온라인 저지 문제를 풀었다. 2주 동안 문제를 풀다보니 게임을 하고 싶어졌고, 마침 민혁이를 이용해서 게임을 하기로 했다.

상근이의 게임은 R×C 보드를 세워놓은 상태에서 진행한다. 맨 처음에 각 정사각형 칸은 비어있거나 벽으로 막혀있다. 상근이는 민혁이에게 돌을 떨어놓을 열을 지시하고, 민혁이는 가장 윗 행의 그 열에 돌을 놓는다. 돌을 놓은 이후에는 중력에 의해서 돌이 떨어지게 된다.

돌에 작용하는 중력은 다음과 같다.

돌의 아랫칸이 벽으로 막혀있거나 가장 아랫줄이라면, 돌은 그 자리에 그대로 멈춰 있는다.

돌의 아랫칸이 비어있다면, 돌은 아랫칸으로 이동한다.

돌의 아랫칸에 돌이 있다면, 돌은 다음과 같이 미끄러진다.
1. 만약 돌의 왼쪽 칸과 왼쪽-아래 칸이 비어있다면, 돌은 왼쪽으로 미끄러진다.
만약 돌이 왼쪽으로 미끄러지지 않았고, 오른쪽 칸과 오른쪽-아래 칸이 비어있다면, 돌은 오른쪽으로 미끄러진다.
2. 위의 두 경우가 아니라면 돌은 그 자리에 멈추고, 다시는 움직이지 않는다.
3. 민혁이는 돌의 이동이 멈춘 이후에 다른 돌을 던지기 시작한다.

보드의 초기 상태와 민혁이가 돌을 놓은 열의 번호가 순서대로 가 주어졌을 때, 모든 돌을 던진 이후에 보드의 상태를 구하는 프로그램을 작성하시오.

민혁이는 항상 제일 윗 칸이 비어있는 칸에만 돌을 던진다.

입력

첫째 줄 : 보드의 크기 R과 C. (1 ≤ R ≤ 30,000, 1 ≤ C ≤ 30).
이후 R 줄 : 보드의 초기 상태.
- . : 빈 칸.
- X : 벽.
다음 줄 : 돌을 던지는 횟수 N. (1 ≤ N ≤ 100,000)
다음 N 줄 : 돌을 던질 열의 위치. (가장 왼쪽 열의 번호는 1번)

출력

총 R개 줄에 걸쳐서 보드의 게임이 모두 끝난 후의 상태.
- O : 돌.

입출력 예

Input	Output
5 4 .... .... X... .... .... 4 1 1 1 1	.... O... X... .... OOO.

◾ 풀이

1. 해설

각 열에 돌을 던질 때 이동하는 경로를 저장하여 빠르게 탐색.(스택을 사용해 마지막 경로부터 확인.)
- 마지막 경로에서 탐색.
- 경로 중 이미 돌이 있는 경우 : 삭제.
- 경로가 없을 경우 : 처음부터 탐색.

2. 프로그램

데이터 입력(R, C, boadr).
돌을 던지는 열 입력.(c)
돌의 최종 위치 탐색. : 경로의 마지막부터 탐색.
- 이미 돌이 있는 경우(반복) : 삭제.
- 경로가 없는 경우 : 처음 위치(1행 c열)에서 탐색 시작.
- 경로가 있는 경우 : 마지막 위치에서 탐색 시작.
위치 탐색.
- 범위를 벗어나거나 벽이 아래에 있는 경우 : 종료.
- 아래에 돌이 있는 경우
  1. 왼쪽이 빈 경우 : 왼쪽으로 이동.
  2. 오른쪽이 빈 경우 : 오른쪽으로 이동.
  3. 빈 곳이 없는 경우 : 종료.
- 빈 공간인 경우 : 아래로 이동.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

// 플래티넘 문제.
// [백준 3025번 돌던지기(https://www.acmicpc.net/problem/3025)].

// 좌표 클래스
class P {
	int row;	// 행
	int col;	// 열

	public P(int row, int col) {
		super();
		this.row = row;
		this.col = col;
	}
}

public class Main {
	static int R, C;	// 행, 열 크기.
	public static char[][] board;	// 보드 행렬.
	public static Deque<P>[] info;	// 각 열에 돌을 던질 시 경로.

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		// 행렬 크기.
		st = new StringTokenizer(in.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());

		// 보드 초기화.
		board = new char[R + 1][C + 1];
		info = new Deque[C + 1];
		for (int i = 0; i <= C; i++) {
			info[i] = new LinkedList<>();
		}

		// 보드 입력.
		for (int i = 1; i <= R; i++) {
			char[] input = in.readLine().toCharArray();
			for (int j = 0; j < C; j++) {
				board[i][j + 1] = input[j];
			}
		}
		
        // 돌 던지기.
		int n = Integer.parseInt(in.readLine());
		for (int step = 0; step < n; step++) {
			int c = Integer.parseInt(in.readLine());

			// 돌을 던질 때 이동 경로에 이미 돌이 있는 경우 꺼냄.
			while (!info[c].isEmpty()
					&& board[info[c].peekLast().row][info[c].peekLast().col] == 'O') {
				info[c].pollLast();
			}
			
            // 경로가 비었다면 : 첫 위치에서 시작.
			if (info[c].isEmpty())
				search(1, c, c);
            // 경로가 있다면 : 마지막 경로에서 시작.
			else
				search(info[c].peekLast().row, info[c].peekLast().col, c);
		}

		
		for (int i = 1; i <= R; i++) {
			for (int j = 1; j <= C; j++) {
				sb.append(board[i][j]);
			}
			sb.append("\n");
		}

		System.out.println(sb);
	}
	
    // 돌의 최종 위치를 탐색하는 함수.
    // - 이동하는 위치는 info[input]에 추가.
    // row : 현재 행.
    // col : 현재 열.
    // input : 돌을 던진 열.
	public static void search(int row, int col, int input) {
    	// 범위를 벗어나거나 벽일 경우 : 종료.
		while (row + 1 <= R && board[row + 1][col] != 'X') {
        	// 돌일 경우
            // 1. 왼쪽 이동.
            // 2. 오른쪽 이동.
            // 3. 멈춤.
			if (board[row + 1][col] == 'O') {
            	// 왼쪽이 비었다면 이동.
				if (col - 1 > 0 && board[row + 1][col - 1] == '.' && board[row][col - 1] == '.') {
					row++;
					col--;
                // 오른쪽이 비었다면 이동.
				} else if (col + 1 <= C && board[row + 1][col + 1] == '.' && board[row][col + 1] == '.') {
					row++;
					col++;
                // 왼쪽과 오른쪽이 비어있지 않다면 멈춤.
				} else break;
            // 돌이 아닐 경우 이동.
			} else row++;
			
            // 경로 추가.
			info[input].offerLast(new P(row, col));
		}
		
        // 최종 위치에 돌 추가.
		board[row][col] = 'O';
	}
}