[백준 3025] 돌 던지기

3025번: 돌 던지기

 

---

 

처음으로 풀어보는 플레티넘 문제이다!

처음에 java로 falling이라는 재귀로 돌이 굴러떨어질때마다 시뮬레이션을 했더니 시간초과가 났다.

시간초과 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static int R, C, N, command;
	static char[][] map;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
		String[] input = br.readLine().split(" ");	
		R = Integer.parseInt(input[0]);				
		C = Integer.parseInt(input[1]);				
		map = new char[R][C];						
		for (int i = 0; i < R; i++) {
			map[i] = br.readLine().toCharArray();	
		}

		N = Integer.parseInt(br.readLine());		
		for (int i = 0; i < N; i++) {
			command = Integer.parseInt(br.readLine())-1;	
			if (map[0][command] != '.') {					
				continue;									
			}
			falling(-1, command); // 화산탄 떨어뜨리기 수행
		}

		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				sb.append(map[i][j]);
			}
			sb.append("\n");
		}
		System.out.println(sb.toString());
	}

	// 화산탄이 떨어지는 것을 수행하는 함수
	static void falling(int x, int y) {
		while (true) {							
			x++; // 아래로 한칸 떨어뜨리기
			if (x >= R || map[x][y] == 'X') { // 땅이거나 장애물에 막혀있다면 굳힘
				map[x - 1][y] = 'O';
				return;
			}
			if (map[x][y] == 'O') {	// 화산탄이라면 멈춤
				break;
			}
		}

		if (0 <= y - 1 && map[x][y - 1] == '.' && map[x - 1][y - 1] == '.') {	// 왼쪽 인덱스 범위 확인 & 왼쪽, 왼쪽-아래칸 비어있는지 확인
			falling(x, y - 1);		// 왼쪽 아래칸으로 굴러 떨어지기 수행
		} else if (y + 1 < C  && map[x][y + 1] == '.' && map[x - 1][y + 1] == '.') { // 오른쪽 인덱스 범위 확인 & 오른쪽, 오른쪽-아래칸 비어있는지 확인
			falling(x, y + 1);		// 오른쪽 아래칸으로 굴러 떨어지기 수행
		} else {	// 왼쪽 오른쪽으로 굴러 떨어지지 않는다면 굳힘
			map[x - 1][y] = 'O';
		}
	}

}

 

아무리 생각해도 개선할 방법이 떠오르질 않아서 다른 분들의 코드를 참고했다.

매번 화산탄이 떨어질때마다 시뮬레이션 한다면 첫번째 떨어지는 화산탄 경로와 두번째 떨어지는 화산탄 경로는 거의 비슷하다.

따라서 경로를 저장해놓고 사용하는 것이 이 문제의 핵심이다.

 

1. 넣을 col에 경로가 저장되어 있지 않다면, 시뮬레이션
2. 경로가 저장되어 있다면, 빈칸이 나올때까지 마지막 요소를 pop한다.
3. 빈칸이 나왔다면 그곳에서 다시 시뮬레이션 해준다.

예시를 들어 설명해보겠다. 문제에 있는 예시를 약간 변형해보았다.

배열은 인덱스 0부터 시작이므로 입력값에서 1 빼주는 것을 잊지말자.

6 4
....
....
..XX
....
XX.X
7
3
3
3
3
2
2
3

 

import sys
input = sys.stdin.readline

R, C = map(int, input().split())
arr = []
checkpoint = [[] for _ in range(C)]
for _ in range(R):
    arr.append(list(input().rstrip()))
N = int(input())


def falling(x, y, line):
    while True:
        checkpoint[line].append([x, y])
        if x+1 == R or arr[x+1][y] == "X":
            arr[x][y] = "O"
            return
        if arr[x+1][y] == "O":
            if y-1 >= 0 and arr[x][y-1] == "." and arr[x+1][y-1] == ".":
                y -= 1
            elif y+1 < C and arr[x][y+1] == "." and arr[x+1][y+1] == ".":
                y += 1
            else:
                arr[x][y] = "O"
                return
        x += 1


for _ in range(N):
    _input = int(input())-1
    
    # 경로 저장이 되어 있다면
    while checkpoint[_input]:
        cx, cy = checkpoint[_input][-1]
        # 마지막 요소가 빈칸인지 확인 아니라면 빼버리기
        if arr[cx][cy] == '.':
            break
        checkpoint[_input].pop()

	# 마지막 요소부터 떨어지기 or 처음부터 떨어지기 수행
    if checkpoint[_input]:
        cx, cy = checkpoint[_input].pop()
        falling(cx, cy, _input)
    else:
        falling(0, _input, _input)

	# 도착지점 O표시 해주기
    cx, cy = checkpoint[_input].pop()
    arr[cx][cy] = "O"

for a in arr:
    print("".join(a))