[백준] 17837: 새로운 게임 2(C++)

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

17837번: 새로운 게임 2

어렵진 않지만 깔끔하게 풀기 어려운 문제이다. 나 또한 아주 더럽게 풀었기 때문에 소스코드를 보고 싶은 분이라면 다른 곳을 찾아 주세요.

소요 시간

오래 걸렸습니다. 골드 2 기준 1시간 40분이 걸렸는데, 자잘한 실수가 잦아 디버깅에 많은 시간을 소요했기 때문입니다.

아마 님들은 더 빨리 푸실 수 있을 것 같아요. 새로운 게임 1 이라는 문제도 있다고 하는데 그걸 풀었다면 좀 더 빨리 풀 수 있을지도...

이러면 안되는데 큰일이다

 

문제 파악

1. 시뮬레이션 규칙

- 특히, 파란색 영역에서의 규칙이 중요하다.

 

구상

딱히 구상이라고 할만한 게 없다.

1. 1~K에 대해,

 1-1. 자기 위에 놓인 말들을 파악하고

 1-2. 위에 놓은 말들과 함께 자신의 이동방향에 맞게 움직인다.

vector를 잘 쓰는지 테스트하는 문제나 다름없었다. 나의 경우 insert를 많이 썼다.

맵의 정보를 3차원 pair 백터로 관리했는데 3차원 + 0.25초의 부담감이 있었다. 찾아보니 다들 비슷하게 한 것 같아 다행이다.

 

#include <string>
#include <vector>
#include<iostream>
#include <climits>
#include<queue>
#include<cmath>
#include<algorithm>

using namespace std;
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
vector<vector<vector<pair<int, int> > > > stone_map;

bool isOver(vector<vector<int> >& stones) {
    //턴이 진행되던 중에 말이 4개 이상 쌓이는 순간 게임이 종료된다.
    return true;
}

bool move(vector<vector<int> >& board, int num, vector<vector<int> >& stones) {
    int idx = 0; 
    int r, c, dir;
    r = stones[num][0]; c = stones[num][1]; dir = stones[num][2];

    for(idx=0; idx<stone_map[r][c].size(); idx++) {
        if(stone_map[r][c][idx].first == num) {
            break;
        }
    }
    vector<pair<int, int> > uppers(stone_map[r][c].begin()+idx, stone_map[r][c].end());
    stone_map[r][c] = vector<pair<int, int> >(stone_map[r][c].begin(), stone_map[r][c].begin() + idx);

    int nr = r + dx[dir-1]; int nc = c + dy[dir-1]; int ndir = dir;

    //체스판을 벗어나는 경우에는 파란색과 같은 경우이다.
    if(nr < 0 || nr > board.size()-1 || nc < 0 || nc > board.size()-1 || board[nr][nc] == 2) {
        if(ndir == 1 || ndir == 3) ndir += 1;
        else ndir -= 1;
        //파란색인 경우에는 A번 말의 이동 방향을 반대로 하고 한 칸 이동한다.
        int nnr = r + dx[ndir-1]; int nnc = c + dy[ndir-1];
        nr = nnr; nc = nnc;
    }
    //방향을 반대로 바꾼 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 가만히 있는다.
    if(nr < 0 || nr > board.size()-1 || nc < 0 || nc > board.size()-1 || board[nr][nc] == 2) {
        nr = r; nc = c;
    }
    else if(board[nr][nc] == 1) {
        reverse(uppers.begin(), uppers.end());
    }


    //이동 준비 끝, 이동하기
    for(int i=0; i<uppers.size(); i++) {
        vector<int> new_stone; new_stone.push_back(nr); new_stone.push_back(nc);
        if(uppers[i].first == num) {
            new_stone.push_back(ndir);
            uppers[i].second = ndir;
        }
        else new_stone.push_back(stones[uppers[i].first][2]);
        stones[uppers[i].first] = new_stone;
    }
    stone_map[nr][nc].insert(stone_map[nr][nc].end(), uppers.begin(), uppers.end());

    if(stone_map[nr][nc].size() > 3) return false;
    return true;
}

int solution(vector<vector<int> >& board, vector<vector<int> >& stones) {
    int answer = 0; //몇 번 턴을 진행중인지
    stone_map.resize(board.size());
    for(int i=0; i<stone_map.size(); i++) {
        stone_map[i].resize(board.size());
    }
    for(int i=0; i<stones.size(); i++) {
        stone_map[stones[i][0]][stones[i][1]].push_back(pair<int, int>(i, stones[i][2]));
    }
    /*
    턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다.
    */
    bool isOver = false;
    while(!isOver) {
        answer ++;
        //1번 말부터 K번 말까지 순서대로 이동
        for(int i=0; i<stones.size(); i++) {
            if(!move(board, i, stones)) {
                isOver = true;
                break;
            }
        }
        if(answer > 1000) return -1;
    }

    return answer;
}

int main(int argc, char** argv)
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n, k;
    cin >> n >> k;
    vector<vector<int> > board;
    board.resize(n);
    for(int i=0; i<n; i++) {
        board[i].resize(n);
    }
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            cin >> board[i][j];
        }
    }
    vector<vector<int> > stones;
    stones.resize(k);
    for(int i=0; i<k; i++) {
        stones[i].resize(3);
        cin >> stones[i][0] >> stones[i][1] >> stones[i][2];
        stones[i][0] -= 1;
        stones[i][1] -= 1;
    }
    int answer = solution(board, stones);
    cout << answer << "\n";

    return 0;
}

 

느낀 점

vector 사용법에 대해 정리할 필요가 있다.