BOJ 3025: 돌 던지기 (미해결)

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

3025번: 돌 던지기

최근 구현능력이 많이 떨어지는 것을 느껴 시뮬레이션/구현 문제를 풀던 중 재밌는 문제를 찾았다.

간단하게 요약하자면 위에서 돌을 떨어뜨렸을 때 돌을 적절히 굴려주고 최종 결과를 출력해주는 문제이다.

 

사실 처음 어떻게 접근할까 고민하던중 최근 set을 이용하여 해결했던 문제가 있어 set을 이용하여 아래와 같은 방법으로 구현하였다.

1. 각 set에는 가장 처음 벽의 위치를 저장한다.
2. 벽의 위치를 저장후 맨 밑칸의 아랫칸을 벽의 위치로 저장한다.
3. 이후 돌을 굴릴때마다 set을 이용하여 가장 가까운 위치를 찾고 조건에 따라 돌을 멈추거나 왼쪽 또는 오른쪽으로 굴려준다.

위와 같이 코드를 짰을 때, 가장 처음 생각했던 시간 복잡도는 query를 입력받는 횟수인 $n$ 그리고 행의 개수 $30$ 각 행을 set을 이용하여 관리하므로 $logr$번 계산을 하게 되므로 총 $O(n \cdot 30 \cdot logr) = O(n logr)$정도가 나오지 않을까 생각했다.

수가 크지 않기 때문에 충분히 빠른 시간 안에 문제를 해결할 수 있으리라 생각했지만 TLE를 받았다.

TLE를 받은 코드는 아래와 같다.

#include<bits/stdc++.h>
using namespace std;
set<int> seq[33];
char board[30303][33];
int main(){
    char msg[30303];
    int r, c; scanf("%d %d", &r, &c);
    for(int i = 0; i<r; ++i){
        scanf("%s", board[i]);
        for(int j = 0; j<c; ++j){
            if(board[i][j] == 'X')
                seq[j].insert(i);
        }
    }
    for(int i = 0; i<c; ++i){
        seq[i].insert(r);
        board[r][i] = 'X';
    }
    int n; scanf("%d", &n);
    for(int i = 0; i<n; ++i){
        int num; scanf("%d", &num);
        --num;
        auto it = seq[num].begin();
        int cur = *it;
        while(1){
            it = seq[num].lower_bound(cur);
            cur = *it;
            --cur;
            if(board[cur + 1][num] == 'X'){
                board[cur][num] = 'O';
                seq[num].insert(cur);
                break;
            }
            else if(0 < num && board[cur][num - 1] == '.' && board[cur + 1][num - 1] == '.')
                --num;
            else if(num < c - 1 && board[cur][num + 1] == '.' && board[cur + 1][num + 1] == '.')
                ++num;
            else{
                board[cur][num] = 'O';
                seq[num].insert(cur);
                break;
            }
        }
    for(int i = 0; i<r; ++i)
        printf("%s\n", board[i]);
    }
}

왜 TLE를 받을까, 도대체 어떤 케이스가 있길래 시간 초과를 받을까라고 고민을 해보던 찰나에 아래와 같은 테스트 케이스를 생각해봤다.

..................
..................
X.................
..................
..................
.X................
..................
..................
X.................
..................
..................
.X................
..................
..................
X.................
..................
..................
.X................

         .
         .
         .

위의 테스트 케이스에서 돌을 1번 칸에 계속 굴려 아래와 같은 상황이 됐다고 가정해보자.

..................
O.................
X.................
..................
.O................
.X................
..................
O.................
X.................
..................
.O................
.X................
..................
O.................
X.................
..................
.O................
.X................

         .
         .
         .

이러한 케이스에서 1번 라인에 돌을 굴리게 되면 최악의 경우 행의 개수만큼 좌우로 움직이며 이동하는 것이 아닌 좌우로 약 1만번 가량까지 움직일 수 있다. 그렇다면 결국 위의 코드의 시간 복잡도는 $O(n \cdot 30 \cdot logr) = O(n logr)$가 아닌 $O(n \cdot 10000 \cdot logr) = O(n logr)$로 제법 큰 상수를 갖는 시간 복잡도가 되어 TLE를 받게 된다.

 

따라서 이를 해결하기 위해 아래와 같은 풀이 과정을 생각해봤다. 간단하게 풀이를 설명하자면 돌을 놓을 수 있는 위치를 set을 이용하여 관리하는 것이 아닌, 특정 칸에 돌을 놓으면 내려가며 하나씩 검사하는 것이 아닌 한번에 가장 끝 지점에 도달할 수 있도록 만드는 것이다.

1. 먼저 모든 입력을 받은 후 각 칸에 돌을 놓았을 때 돌이 놓일 위치를 저장해둔다. 이때 맨처음 입력으로는 '.'과 'X'만 주어지므로 벽의 바로 위에 돌이 놓이게 되므로 입력을 받으며 처리할 수 있다.
2. 1번의 돌을 놓았을 때 돌이 놓일 위치를 인접 리스트로 관리하며 해당 위치에 돌이 놓인 경우 해당 간선을 제거하고 다시 돌을 놓을 수 있는 곳을 탐색한다.

위의 방법을 직접 구현해본 것은 아니지만 인접 리스트를 관리하며 간선을 추가/삭제하기 위해 제법 많은 시간이 소요되리라 생각한다.

따라서 위의 방법과 set을 이용하는 방법을 적절히 섞어 좌우를 반복하여 돌아다니며 돌이 놓을 위치를 탐색하는 것이 아닌, 특정 위치에 돌을 놓으면 바로 돌이 놓일 수 있는 방법을 아직 고민중이다.