[백준] 3025: 돌 던지기 - JAVA

in Algorithm on 구현

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

풀이

주어진 조건에 맞게 위에서부터 돌을 떨어뜨려 최종 상태를 출력하는 문제였다.

단순한 구현으로 하나씩 진행하며 문제를 풀었을 때는 시간초과가 발생했다.

시간초과를 해결하기위해 메모이제이션을 해야했다.

처음 돌을 놓는 열 별로 stack을 만들어 돌이 이동하는 경로를 저장했다.

새로운 돌을 던질 때 stack에 경로가 들어있다면 마지막에서부터 진행하면 된다.

1. 돌의 아랫칸이 벽으로 막혀있거나 가장 아랫줄이라면, 돌은 그 자리에 그대로 멈춰 있는다.
2. 돌의 아랫칸이 비어있다면, 돌은 아랫칸으로 이동한다.
3. 돌의 아랫칸에 돌이 있다면, 돌은 다음과 같이 미끄러진다.
    1. 만약 돌의 왼쪽 칸과 왼쪽-아래 칸이 비어있다면, 돌은 왼쪽으로 미끄러진다.
    2. 만약 돌이 왼쪽으로 미끄러지지 않았고, 오른쪽 칸과 오른쪽-아래 칸이 비어있다면, 돌은 오른쪽으로 미끄러진다.
    3. 위의 두 경우가 아니라면 돌은 그 자리에 멈추고, 다시는 움직이지 않는다.

위의 조건에 따라 drop 메서드를 구현했다.

drop메서드에서 r, c를 Point 클래스로 stack에 넣어가면서 진행했다.

메모리: 85140KB

시간: 808ms

언어: Java 11

코드

import java.io.*;
import java.util.*;

public class Main {
    static class Point {
        int r;
        int c;

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    static int R, C;
    static char[][] board;
    static Stack<Point>[] stack;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        board = new char[R + 1][C + 1];
        for (int i = 1; i <= R; i++) {
            String s = br.readLine();
            for (int j = 1; j <= C; j++) {
                board[i][j] = s.charAt(j - 1);
            }
        }

        stack = new Stack[C + 1];
        for (int i = 1; i <= C; i++) {
            stack[i] = new Stack<>();
        }

        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            int col = Integer.parseInt(br.readLine());

            while (!stack[col].isEmpty() &&
                    board[stack[col].peek().r][stack[col].peek().c] == 'O') {
                stack[col].pop();
            }

            if (stack[col].isEmpty()) {
                drop(1, col, col);
            } else {
                drop(stack[col].peek().r, stack[col].peek().c, col);
            }
        }

        StringBuilder sb = new StringBuilder();
        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);
    }

    private static void drop(int r, int c, int col) {
        stack[col].push(new Point(r, c));

        // 돌의 아랫칸이 벽으로 막혀있거나 가장 아랫줄이라면, 돌은 그 자리에 그대로 멈춰 있는다.
        if (r + 1 <= R && board[r + 1][c] == 'X') {
            board[r][c] = 'O';
        } else if (r == R) {
            board[r][c] = 'O';
        }

        // 돌의 아랫칸이 비어있다면, 돌은 아랫칸으로 이동한다.
        else if (r + 1 <= R && board[r + 1][c] == '.') {
            drop(r + 1, c, col);
        }

        // 돌의 아랫칸에 돌이 있다면,
        else if (r + 1 <= R && board[r + 1][c] == 'O') {
            // 만약 돌의 왼쪽 칸과 왼쪽-아래 칸이 비어있다면, 돌은 왼쪽으로 미끄러진다.
            if (check(r, c - 1) && check(r + 1, c - 1) && board[r][c - 1] == '.' && board[r + 1][c - 1] == '.') {
                drop(r + 1, c - 1, col);
            }

            // 만약 돌이 왼쪽으로 미끄러지지 않았고, 오른쪽 칸과 오른쪽-아래 칸이 비어있다면, 돌은 오른쪽으로 미끄러진다.
            else if (check(r, c + 1) && check(r + 1, c + 1) && board[r][c + 1] == '.' && board[r + 1][c + 1] == '.') {
                drop(r + 1, c + 1, col);
            }

            // 위의 두 경우가 아니라면 돌은 그 자리에 멈추고, 다시는 움직이지 않는다.
            else {
                board[r][c] = 'O';
            }
        }
    }

    private static boolean check(int r, int c) {
        if (r < 1 || c < 1 || r > R || c > C) {
            return false;
        }
        return true;
    }
}