[BOJ 3025] 돌 던지기

문제 링크

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

3025번: 돌 던지기

시뮬레이션 문제는 많이 다뤄서 자신있었는데 시간초과를 해결하는데 오래 걸린 문제다

순진하게 구현했다가는 O(RN)으로 TLE를 맞기 십상이다 (_ㅠㅠ_)

O(RN)에서 쿼리수에 해당하는 N을 줄일 순 없다

N개의 각 쿼리당 곱해지는 O(R)을 줄이는 방법을 생각해보자

---

아이디어

 

 

기본

하나의 열 안에서 돌이 'O'나 'X'를 만나기 전까지 떨어지는 것을 시뮬레이션의 한 단위라고 생각해보자

 

돌이 'X'를 만나는 경우를 생각해보자

'X'를 만나면 돌은 구르지 않고 그 위치에 놓인다

 

돌이 'O'를 만나는 경우를 생각해보자

'O'를 만나서 왼쪽으로 구를 수 있으면 왼쪽 열에서 다음 시뮬레이션을 하고

'O'를 만나서 오른쪽으로 구를 수 있으면 오른쪽 열에서 다음 시뮬레이션을 하고

'O'를 만나서 좌우로 구를 수 없다면 그 위치에 돌이 놓인다

 

이렇게 주먹구구식으로 시뮬레이션을 돌린다면 O(RN)일 것이다

 

개선1

돌을 (row, col)에서 떨어트릴 때 처음으로 돌이 놓이는 빈 칸을 어떻게 빠르게 알 수 있을까?

가장 위의 행을 1, 맨 아래 바닥을 R이라고 할 때

시뮬레이션을 하면서 c열에서 벽 또는 돌이 있는 행의 위치를 set에 저장한다면 logN으로 구할 수 있다

 

set<int>top[c] : c열에 있는 장애물의 행이라고 하면

(row, col)에서 떨어뜨린 돌은 (*top[col].upper_bound(row)) 행에서 처음으로 벽 또는 돌에 부딪힌다

여기까지를 코드로 살펴보자

소스코드

#include <cstdio>
#include <vector>
#include <set>
using namespace std;

int r, c, q;
char b[30003][33], tmp[2];
set <int> top[32];

void simulate(int row, int col)
{
    int h = *(top[col].upper_bound(row));

    if (b[h][col] == 'X') {
        b[h - 1][col] = 'O';
        top[col].insert(h - 1);
    }
    else {
        if (b[h][col-1] == '.' && b[h - 1][col-1] == '.') {
            simulate(h - 1, col - 1);
        }
        else if (b[h][col + 1] == '.' && b[h - 1][col + 1] == '.') {
            simulate(h - 1, col + 1);
        }
        else {
            b[h - 1][col] = 'O';
            top[col].insert(h - 1);
        }
    }
}

void output()
{
    for (int i = 1; i <= r; ++i)
        printf("%s\n", b[i] + 1);
}

int main()
{
    scanf("%d %d", &r, &c);
    for (int i = 1; i <= r; ++i) {
        for (int j = 1; j <= c; ++j) {
            scanf("%1s", &tmp);
            b[i][j] = tmp[0];
            if (b[i][j] == 'X')
                top[j].insert(i);
        }
    }
    for (int i = 1; i <= c; ++i) {
        top[i].insert(r + 1);
    }

    scanf("%d", &q);
    while (q--) {
        int col; scanf("%d", &col);
        simulate(1, col);
    }
    output();
    return 0;
}

 

위의 코드는 문제점이 있다

 

     개선1        소스코드   TLE 반례

위와 같은 패턴의 30000 * 2 보드를 생각해보자

simulate()은 한 번 호출 할 때마다 기껏해야 3개의 행밖에 내려가지 못한다

그래서 결국 똑같은 O(RN)의 시간복잡도를 갖는다

 

개선2

특정 열에서 돌이 굴러가는 경로를 계산해 두고, 다음번 시뮬레이션 때

다음번 돌이 놓일 위치가 다른 열에서 굴러 떨어진 돌에 의해 막혀 있다면

경로를 따라 한 칸씩 거슬러 올라와 빈칸부터 다시 시뮬레이션 하자

 

어떻게하면 더 빠르게 C열에 놓은 돌이 어디에 떨어지는지 알 수 있을까?

30000행짜리의 보드에서 어떤 C열에 두 번 돌을 놓는다고 생각해보자

개선1의 코드는 빠르게 내려간다고는 하지만 결국 첫 시뮬레이션과 두 번째 시뮬레이션에서 겹치는 과정이 많다

이 중복되는 연산이 시간초과의 핵심이다

생각을 전환해 아래에서 위로 올라오는식으로 따져보자

 

개선1에서의 설명을 되짚어보면,

1행에서 떨어뜨린 돌은 또 다른 돌이나 벽을 만날 때 까지 떨어진다

이 때, 돌이 부딪히며 왼쪽 또는 오른쪽으로 구르기 전의 그 위치를 체크포인트라고 해보자

 

맨 처음 c열에서 돌을 떨어뜨릴 때 simulate()함수를 통해 벽을 만날 때까지 돌이 떨어지고

떨어지는 과정에서 "1행 c열에서 떨어뜨린 돌"의 체크포인트가 만들어진다

그러면 그 다음부터 "1행 c열에 떨어뜨리는 돌"은 모두 그 전의 "1행 c열에서 떨어뜨린 돌"의 체크포인트를 똑같이 지난다

(사실 이 부분에서 다른 행에서 놓은 돌이 쌓이면서 "1행 c열에서 떨어뜨린 돌"이 지나는 경로가 바뀌는 반례가 있지 않을까 생각했는데 열심히 종이에 그려봐도 찾을 수 없어서 믿음의 구현을 시작했다..)

 

아무튼 이제, 1행 c열에서 돌을 놓는다면 그 전에 1행 c열에서 놓은 돌이 지나간 체크포인트 중에서

마지막 체크포인트부터 '.'인 칸을 찾아서 역으로 올라가며 다음에 놓여질 돌의 위치를 빠르게 찾을 수 있다

 

rec[origin][idx] : 최초에 origin열에서 떨어뜨린 돌의 idx번째 체크포인트 좌표

idx[origin] : 최초에 origin열에서 떨어뜨린 돌의 체크포인트 개수

 

+ 시뮬레이션을 하며 새로운 장애물을 set에 insert해줄 때,

그 아래 칸의 장애물은 set에서 지워줘도 상관 없기 때문에 지워주었습니다 ( top[col].erase(h-1) )

+ rec은 저 같은 경우 vector로 했지만 stack으로 사용해도 좋겠습니다

---

소스코드

#include <cstdio>
#include <vector>
#include <stack>
#include <set>
using namespace std;
using pii = pair<int, int>;

int r, c, q;
char b[30003][33], tmp[2];
set <int> top[33];
pii rec[33][30003];
int idx[33];

//origin : 최초에 어느 열에서 떨어뜨린건지
//row, col : 떨어뜨릴 돌의 현재 행과 열
void simulate(int row, int col, int origin)
{
    // (row, col) 에서 떨어져 처음 부딪히는 가장 높은 빈칸의 높이
    int h = *(top[col].upper_bound(row));

    if (b[h][col] =='O') {
        if (b[h][col - 1] == '.' && b[h - 1][col - 1] == '.') {
            rec[origin][idx[origin]] = { h - 1, col };
            idx[origin]++;
            simulate(h - 1, col - 1, origin);
        }
        else if (b[h][col + 1] == '.' && b[h - 1][col + 1] == '.') {
            rec[origin][idx[origin]] = { h - 1, col };
            idx[origin]++;
            simulate(h - 1, col + 1, origin);
        }
        else {
            b[h - 1][col] = 'O';
            top[col].erase(h);
            top[col].insert(h - 1);
        }
    }
    else {
        b[h - 1][col] = 'O';
        top[col].erase(h);
        top[col].insert(h - 1);
    }
}

void output()
{
    for (int i = 1; i <= r; ++i)
        printf("%s\n", b[i] + 1);
}

int main()
{
    scanf("%d %d", &r, &c);
    for (int i = 1; i <= r; ++i) {
        for (int j = 1; j <= c; ++j) {
            scanf("%1s", &tmp);
            b[i][j] = tmp[0];
            if (b[i][j] == 'X')
                top[j].insert(i);
        }
    }
    for (int i = 1; i <= c; ++i) {
        top[i].insert(r + 1);
    }

    scanf("%d", &q);
    while (q--) {
        int col; scanf("%d", &col);

        int r, c;
        while (idx[col] > 0) { // col열에서 떨어뜨린 돌의 체크포인트 개수
            r = rec[col][idx[col]-1].first;
            c = rec[col][idx[col]-1].second;
            if (b[r][c] != '.')
                --idx[col];
            else break;
        }
        if (idx[col] == 0) {   // '.'인 체크포인트가 없으면 처음부터 시뮬레이션
            simulate(1, col, col);
        }
        else {                 // '.'인 체크포인트가 있으면 그 지점에서부터 시뮬레이션
            simulate(r, c, col);
        }
    }
    output();
    return 0;
}

 

 

 

 

공부한 것을 정리하기 위한 기록입니다.

틀린 부분이 있다면 부드럽게 알려주세요.