[ BOJ - 17837번 ] 새로운 게임 2 (C++)

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

 

 최대 반복 횟수는 1000, 체스판의 최대 크기는 12x12, 말의 최대 개수는 10이므로 탐색에만 약 1000만 번의 연산이 필요하다.

따라서 각 반복별로 말의 이동을 처리하는 기능을 위해 O(n)의 시간만 추가로 사용할 수 있을 것이다.

 

[ 풀이 방법 ]

1. 말을 순서대로 이동시키는 기능

  - 1~K

  - 말의 이동방향을 저장해 사용할 수 있어야 한다.

-> vector를 이용해 말의 좌표와 이동 방향을 저장하는 구조체를 저장하고, 말의 순서는 index로 처리

 

2. 말이 이동하려는 체스판의 칸 색깔에 따라 이동을 다르게 처리하는 기능

  1. 흰색:

  - 말을 이동시킨다.

    - 이동하려는 칸에 이미 말이 있을 경우 가장 위에 올려놓는다.

    - 말의 위에 다른 말들이 올려져 있을 경우, 말의 위에 있는 말들도 함께 이동한다.

  2. 빨간색:

  - 말의 이동 기능은 흰색과 동일하나, 이동하기 전에 말들이 올려진 순서를 반대로 바꾼다.

  3. 파란색:

  - 이동 방향을 반대로 돌린다.

  - 방향 바꾼 뒤 이동해야 할 칸이 파란색이면 이동하지 않는다.

  - 그 외의 경우 이동해야 할 칸의 색깔에 따라 말의 이동을 처리한다.

 

3. 말이 4마리 쌓이거나, 반복횟수가 1000을 넘을 때까지 위 과정을 반복한다.

 

 체스판의 각 칸에 말을 추가하거나 일부의 말을 제거하는 기능, 말 n마리의 순서를 reverse하는 기능이 O(n)의 시간복잡도를 가지도록 구현해야 한다.

=> C++ string의 +연산자와 substr함수, STL의 reverse함수를 이용해 O(n) 시간복잡도를 가지도록 기능들을 구현할 수 있다. 따라서 각 칸에 위치한 말을 순서대로 저장하고 이동 기능을 처리하기 위해 string 자료형을 이용하였다.

 

[ 회고 ]

 말의 이동 기능을 구현할 때, 체스판의 각 칸에 위치한 말과 말의 순서는 업데이트 하였으나 말들의 좌표와 방향을 저장하는 구조체의 배열은 업데이트하지 않아 기능이 올바르게 작동하지 않았다.

 이 문제의 경우 예제 입력이 충분히 제공되어 디버깅을 통해 빠르게 문제의 원인을 찾고 해결할 수 있었지만, 예제 입력이 없었다면 시간이 오래 걸리거나 아예 찾지 못할 수 있었을 것이다.

 

 앞으로 하나의 객체 정보를 담는 컨테이너가 여러개 필요한 문제가 주어진 경우, 빠뜨리지 말고 모든 객체 정보를 업데이트 해야한다는 것을 유의해야 할 것이다.

 

[ 정답 코드 ]

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

#define MAX 12

#define WHITE 0
#define RED 1
#define BLUE 2

using namespace std;

struct Horse {
    int r; int c;
    int dir;
};

int N, K;
vector<vector<int>> colors;
string board[MAX][MAX];
vector<Horse> horse;

int res;
bool flag = false;

int dirR[4] = {0, 0, -1, 1};
int dirC[4] = {1, -1, 0, 0};

void move() {
    
    for(int i = 0; i < horse.size(); i++) {
        
        int k = i;
        int r = horse[i].r;
        int c = horse[i].c;
        int dir = horse[i].dir;
        
        int nr = r + dirR[dir];
        int nc = c + dirC[dir];

        int color;
        if(nr < 0 || nr >= N || nc < 0 || nc >= N) color = BLUE;
        else color = colors[nr][nc];
        
        if(color == WHITE) {
            
            auto it = board[r][c].find(to_string(k));
            string movingHorse = board[r][c].substr(it);
            board[r][c] = board[r][c].substr(0, it);
            board[nr][nc] += movingHorse;
            
        } else if(color == RED) {
            
            auto it = board[r][c].find(to_string(k));
            string movingHorse = board[r][c].substr(it);
            reverse(movingHorse.begin(), movingHorse.end());
            board[r][c] = board[r][c].substr(0, it);
            board[nr][nc] += movingHorse;
            
        } else if(color == BLUE) {
            
            if(dir == 0 || dir == 2) dir += 1;
            else dir = (dir+3)%4;
            horse[k].dir = dir;
            
            nr = r + dirR[dir];
            nc = c + dirC[dir];
            
            int color;
            if(nr < 0 || nr >= N || nc < 0 || nc >= N) color = BLUE;
            else color = colors[nr][nc];
            
            if(color == WHITE) {
                
                auto it = board[r][c].find(to_string(k));
                string movingHorse = board[r][c].substr(it);
                board[r][c] = board[r][c].substr(0, it);
                board[nr][nc] += movingHorse;
                
            } else if(color == RED) {
                
                auto it = board[r][c].find(to_string(k));
                string movingHorse = board[r][c].substr(it);
                reverse(movingHorse.begin(), movingHorse.end());
                board[r][c] = board[r][c].substr(0, it);
                board[nr][nc] += movingHorse;
                
            } else if(color == BLUE) {
                nr = r;
                nc = c;
            }
        }
        
        if(board[nr][nc].length() >= 4) {
            flag = true;
            return;
        }
        
        for(int j = 0; j < board[nr][nc].length(); j++) {
            int k = (board[nr][nc][j] - '0');
            horse[k].r = nr;
            horse[k].c = nc;
        }
    }
}

void solve() {
    
    while(res <= 1000) {
        
        if(flag) break;

        move();
        
        res++;
    }
}

int main() {
    
    iostream::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> K;
    
    colors.resize(N, vector<int>(N));
    
    for(int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> colors[i][j];
        }
    }
    
    for(int k = 0; k < K; k++) {
        int r, c, d;
        cin >> r >> c >> d;
        horse.push_back({r-1, c-1, d-1});
        board[r-1][c-1] += to_string(k);
    }
    
    solve();
    
    if(res > 1000) cout << -1 << '\n';
    else cout << res << '\n';
    
    return 0;
}