[백준] 8972. 미친 아두이노

문제 설명

SWEA에 나올법한 구현 문제이다.

아래의 과정을 통해서 시뮬레이션한 결과를 출력하며, 미친 아두이노와 플레이어(종수)의 아두이노가 동일한 좌표에 위치하면 시뮬레이션을 종료시키고 “kraj X"라는 문자열을 출력한다. (X는 시뮬레이션이 종료된 단계)

먼저, 종수가 아두이노를 8가지 방향(수직,수평,대각선)으로 이동시키거나, 그 위치에 그대로 놔둔다.
종수의 아두이노가 미친 아두이노가 있는 칸으로 이동한 경우에는 게임이 끝나게 되며, 종수는 게임을 지게 된다.
미친 아두이노는 8가지 방향 중에서 종수의 아두이노와 가장 가까워 지는 방향으로 한 칸 이동한다. 즉, 종수의 위치를 $(r1,s1)$, 미친 아두이노의 위치를 $(r2, s2)$라고 했을 때, $|r1-r2| + |s1-s2|$가 가장 작아지는 방향으로 이동한다.
미친 아두이노가 종수의 아두이노가 있는 칸으로 이동한 경우에는 게임이 끝나게 되고, 종수는 게임을 지게 된다.
2개 또는 그 이상의 미친 아두이노가 같은 칸에 있는 경우에는 큰 폭발이 일어나고, 그 칸에 있는 아두이노는 모두 파괴된다.

Solution

이 문제의 핵심은 2개또는 그 이상의 미친 아두이노 존재시 파괴라는 점이다.
이 부분을 염두에 두고 시뮬레이션 코드를 작성해야하는데 본인은 이를 간과하고 알고리즘을 설계했다가 낭패를 봤다.

미친 아두이노가 이동하는 좌표에 다른 미친 아두이노가 존재할때 파괴를 시키면 다음과 같은 경우에서 올바른 결과를 보장하지 못한다.

이동 시 미친 아두이노가 존재하면 파괴 (잘못된 경우)
1. $(3,3)$에서 $(3,2)$로 이동
2. $(2,2)$에서 $(3,2)$로 이동

따라서, 모든 미친 아두이노가 이동 후에 좌표가 겹치는지 여부를 검사한 후 겹친다면 폭팔을 수행해야한다.

올바른 경우
1. $(3,3)$에서 $(3,2)$로 이동
2. $(2,2)$에서 $(3,2)$로 이동
3. $(3,2)$에서 $(4,1)$로 이동
4. 모든 아두이노 이동 후 겹치는좌표 폭팔

수행단계

종수를 이동시킨다.
1. 이동시키고자 하는 위치에 미친 아두이노가 존재하면 return
2. '.' 이라면 종수의 위치 갱신 및 map 갱신(새로운 좌표에 ‘I’ 할당, 기존 좌표에 '.' 할당)
미친 아두이노를 이동시킨다.
1. 8가지 방향 중 $| r1 - r2 | + | s1 - s2 |$가 최소인 방향을 설정한다. (범위를 벗어나는 좌표라면 continue)
2. 이동시키고자 하는 위치에 종수가 존재하면 return
3. 미친 아두이노의 위치만 갱신
미친 아두이노들이 이동한 좌표에서 충돌여부를 검사한다.
1. 충돌이 발생한 미친 아두이노들은 리스트에서 제거
2. 충돌이 발생하지 않은 미친 아두이노들의 위치 값을 통해 map 갱신(새로운 좌표에 ‘R’ 할당, 기존 좌표에 '.' 할당)
1번부터 재반복한다.

Code

코드를 다 작성하고 제출하니 시간초과 판정을 받았다. ~~ㅂㄷㅂㄷ…~~
기존 코드에서는 위 수행단계 3의 과정을위해 아래의 코드로 작성하였는데, 이 경우 각각의 미친 아두이노가 나머지 모든 미친 아두이노와 값을 비교하기 때문에 $O(N^2)$이 소요된다.

//R와 충돌 검사 및 폭팔 처리
for(int i=0; i < crazy.size(); i++){
    if(check[i]) continue;
    bool bomb = false;
    int ty = crazy[i].first;
    int tx = crazy[i].second;

    for(int j=0; j < crazy.size(); j++){
        if(i == j) continue;

        int uy = crazy[j].first;
        int ux = crazy[j].second;
        if(ty == uy && tx == ux){
            check[j] = true;
            bomb = true;
        }
    }

    if(!bomb) map[ty][tx] = CRAZY;
    else check[i] = true;
}

시복잡도를 최소화 시키기 위해 미친 아두이노들의 좌표값들을 정렬해준 후 순회하며 아래의 단계를 수행하는 것으로 변경하였다.

crazy[i]의 충돌여부 검사시 j는 i 인덱스로 설정
crazy[i]와 crazy[j+1]이 같지 않을때까지 j인덱스 증가
i의 인덱스와 j의 인덱스가 같다면 crazy[i]는 충돌이 일어나지 않았으므로 map 갱신 및 새로운 리스트에 삽입
i와 j의 인덱스가 다르다면 i ~ j-1까지는 충돌이 발생. 다음 비교를 위해서 i는 j 인덱스로 변경

따라서 시복잡도는 $O(NlogN)$이 되게된다.

//R와 충돌 검사 및 폭팔 처리
sort(crazy.begin(), crazy.end());
vector<pair<int,int>> temp;
for(int i=0; i < crazy.size(); i++){
    int j = i;

    //충돌이 발생하는 인덱스는 건너뛰기
    while(j < crazy.size() && crazy[i] == crazy[j+1]){ 
        j++;
    }
    if(i==j){ // 충돌이 발생하지 않은 경우
        int cy = crazy[i].first;
        int cx = crazy[i].second;
        map[cy][cx] = CRAZY;
        temp.push_back(crazy[i]);
    }
    else i = j; // 인덱스 변경 (건너뛰기)
}
crazy = temp;

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define LEN 101
#define CRAZY 'R'
#define PLAYER 'I'
#define EMPTY '.'
#define INF 1e9

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int R, C, step = 0;
    vector<string> map;
    pair<int,int> player;
    vector<pair<int,int>> crazy;
    string command;
    bool is_end = false;
    int dx[] = {0,-1,0,1,-1,0,1,-1,0,1}; // 1 ~ 9, 0은 dummy
    int dy[] = {0,1,1,1,0,0,0,-1,-1,-1};

    // 입력
    cin >> R >> C;
    for(int i=0; i<R; i++){
        string row;
        cin >> row;
        map.push_back(row);
        for(int j=0; j<C; j++){
            if(map[i][j] == CRAZY) crazy.push_back({i, j}); // y,x
            if(map[i][j] == PLAYER) player = {i, j};
        }
    }
    cin >> command;

    for(char c : command){
        int cmd = c - '0';

        // 플레이어 이동
        int py = player.first + dy[cmd];
        int px = player.second + dx[cmd];
        step++;

        is_end = map[py][px] == CRAZY; //R과 충돌 검사
        if(is_end) break;

        map[player.first][player.second] = EMPTY;
        map[py][px] = PLAYER;
        player = {py, px};

        //미친 아두이노 이동
        for(int i=0; i < crazy.size(); i++){
            int cy, cx, judge = INF;
            for(int k=1; k<=9; k++){
                if(k==5) continue;
                int ty = crazy[i].first + dy[k];
                int tx = crazy[i].second + dx[k];

                if(0 > ty || ty >= R || 0 > tx || tx >= C) continue;

                int val = abs(py - ty) + abs(px - tx);
                if(judge > val){
                    judge = val;
                    cy = ty;
                    cx = tx;
                }
            }

            is_end = map[cy][cx] == PLAYER; // I와 충돌 검사
            if(is_end) goto escape;

            map[crazy[i].first][crazy[i].second] = EMPTY;
            crazy[i] = {cy, cx};
        }

        //R와 충돌 검사 및 폭팔 처리
        sort(crazy.begin(), crazy.end());
        vector<pair<int,int>> temp;
        for(int i=0; i < crazy.size(); i++){
            int j = i;

            //충돌이 발생하는 인덱스는 건너뛰기
            while(j < crazy.size() && crazy[i] == crazy[j+1]){ 
                j++;
            }
            if(i==j){ // 충돌이 발생하지 않은 경우
                int cy = crazy[i].first;
                int cx = crazy[i].second;
                map[cy][cx] = CRAZY;
                temp.push_back(crazy[i]);
            }
            else i = j; // 인덱스 변경 (건너뛰기)
        }
        crazy = temp;
    }
    escape:;

    if(is_end){
        cout << "kraj " << step;
    }
    else{
        for(int i=0; i<R; i++){
            cout << map[i] << '\n';
        }
    }
}

문제 설명

Solution

수행단계

Code

CATALOG