백준 : 3025 java (돌 던지기)

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

3025번: 돌 던지기

 

시뮬레이션 문제

 

하지만 매 쿼리마다 시작지점에서 도착지점을 찾는다면 for문이 3만번 매번돌아서 시간초과를 발생한다.

 

따라서 현재 쿼리가 j 번째 열이라면 'O' 를 삽입할  행위치와 열위치를 바로 찾을 수 있어야한다.

 

이때 필요한 자료구조는 [R][C] 자료구조에는 지금 C열로 출발 햇을때 R 번째 행에서의 열의 위치를 저장하는 배열이 필요하다.

 

col[x] 는 x위치의 출발햇을 때 타겟(돌멩이가 부딪히는 최종위치) 열을 반환한다.

 

위 그림에서 시작열의 위치가 6 이라면    x의 위치가 r,6 이라고한다면 이차원 배열을 이용하면 col[6] = 6 라는 값을 얻을 수 있고 O(1) 시간으로 'O'를 넣을 수 있는 위치를 찾을 수 있다. 그위치에 O를 삽입하고 난 다음은 어떻게 해야할까??

 

그림으로보면 col[6]의 r의 값은 R-1이 될것이고  열 번호는 5가 되어야한다. 이것을 갱신하기 위해서는 

처음 x의 위치의 r에서 r-1에 O를 삽입하고 r의 위치를 한단계 올린다.

 

그런 다음 좌쪽이 비어있으면 O를 가리키는 r위치에 저장된 열의 값을 -1해준것으로 갱신하고 r값을 1증가시킨다.

 

 

 

그리고 현재 가리키는 5번째 열로 시작햇을때 타겟값인 r과 열의 위치의값이 빈공간이면 현재 열과값 같은 값을 저장하고 r을 1증가시킨다.

 

이렇게 반복하면서 X를 만나거나 R에 도달하거나 좌 우로 움직일 수 없는경우에는 갱신을 종료한다.

 

갱신을 종료한다는 말은 현재 r-1의 위치에 'O'를 삽입하는 위치라는 것

 

소스코드

 

package algo0504;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;
 
public class Main {
    
    static int T;
    static int N;
    static int H[] = new int[100000];
    static int R, C;
    static char map[][] = new char[30000][31];
    static Quick quick[] = new Quick[30];
 
    // 빠른 접근을 위한 class 배열
    static class Quick {
        int col[]; // col[r] 하면 r번째행은 몇번째 열에 있는가 반환
        int r; // 장애물의 위치
 
        public Quick() {
            super();
            this.col = new int[30000];
            this.r = 1;
        }
 
        public void insert() {
            map[r - 1][col[r - 1]] = 'O';
        }
 
        public void trim() {
            while(true) {
                // 장애물 바로위를 가리킨다.
                int cur = col[r-1];
                
                // 만약 그지점이 빈공간이 아니라면 insert한 직후
                // 위로 거슬러 올라가면서 빠른접근하도록 갱신한다.
                if(r >1 && map[r-1][cur] != '.'){
                    r--;
                }
                // 타겟 위치가 맨밑이라는건 갱신할때까지 갓다는것
                else if(r == R)
                    break;
                // X도 갱신할만큼 갱신한것.
                else if(map[r][cur] == 'X')
                    break;
                else if(map[r][cur] == '.')
                    col[r++] = cur;
                else {
                    // 좌
                    if(cur>0 && map[r][cur-1] == '.' && map[r-1][cur-1]=='.') 
                        col[r++] = cur-1;
                    // 우
                    else if( cur+1<C && map[r][cur+1]=='.' && map[r-1][cur+1]=='.')
                        col[r++] = cur+1;
                    // 둘다아니면 갱신끝
                    else 
                        break;
                    
                }
            }
        }
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
 
        st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        for (int i = 0; i < R; i++)
            map[i] = br.readLine().toCharArray();
 
        for (int j = 0; j < C; j++) {
            // 배열을 만들고 j의 위치에서 타겟위치 r의 위치를 갱신해준다.
            quick[j] = new Quick();
            quick[j].col[0] = j;
            quick[j].trim();
        }
 
        N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            H[i] = Integer.parseInt(br.readLine()) - 1;
        }
        
        for( int i=0;i<N;i++) {
            quick[H[i]].insert();
            for(int j=0;j<C;j++)
                quick[j].trim();
        }
        
        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());
 
    }
 
}