[백준 17780 새로운 게임]

A. 접근법

문제풀이 시간 : 약 1시간 40분 소요...(실수만 아니면 1시간 20분쯤 풀었을텐데 ㅜㅜ)

구현과 시뮬레이션 카테고리로 문제 지문에 충실하게 소스코드를 작성하면 정답이 된다.

B. 구현

nxtcan(int x, int y)

(x, y)에 있는 칸이 어떤 칸인지 판별하는 함수.

mov(int x, int y)

(x, y)에 있는 말들을 옮기는 함수이다. 옮기는 도중 겹치는 말이 4개 이상일 경우 true를 반환하고 이외에는 false를 반환.

실수하여 시간을 오래 잡아먹은 곳은 아래의 코드이다.

for(int k = 0; k < K; k++) {
        for(int i = 0 ; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(pan[i][j].size() > 0 && pan[i][j][0].first == k) {
                    if(mov(i, j))
                        return time;
                    break;
                }
            }
        }
    }

k는 말의 번호이고 i, j는 격자의 위치인데 if문에 조건의 충족하고 한번 mov함수를 통해 움직임이 있으면 해당 말 k에 대해서는 탐색을 종료했어야했는데 그렇지 못했다. 만약 (i, j)에 있는 k가 움직여져 (i+1, j)로 이동했을 때, 이후 i가 증가해서 (i+1, j)의 맨 아래의 말이 k라면 k말을 한 턴에 두 번 이상 옮기게 된다.

아래는 수정한 코드입니다.

for(int k = 0; k < K; k++) {
        chk = 0;
        for(int i = 0 ; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(pan[i][j].size() > 0 && pan[i][j][0].first == k) {
                    if(mov(i, j))
                        return time;
                    chk = 1;
                    break;
                }
            }
            if(chk == 1)
                break;
        }
    }

C. 코드

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

using namespace std;
int T, N, K;
vector<vector<int>> table;
vector<vector<vector<pair<int, int>>>> pan;
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
int nxtcan(int x, int y) {
    if(x < 0 || x >= N || y < 0 || y >= N)
        return 2;
    if(table[x][y] == 0)
        return 0;
    else if(table[x][y] == 1)
        return 1;
    else if(table[x][y] == 2)
        return 2;
    else{return -1;}
}
bool mov(int x, int y) {

    int d = pan[x][y][0].second;

    int nx = x + dx[d];
    int ny = y + dy[d];
    int ncan = nxtcan(nx, ny);

    if(ncan == 0) {

        for(auto it: pan[x][y])
            pan[nx][ny].push_back(it);
        pan[x][y].clear();

        if(pan[nx][ny].size() >= 4)
            return true;
    }
    else if(ncan == 1) {
        reverse(pan[x][y].begin(), pan[x][y].end());
        for(auto it: pan[x][y])
            pan[nx][ny].push_back(it);
        pan[x][y].clear();

        if(pan[nx][ny].size() >= 4)
            return true;
    }
    else if(ncan == 2) {

        if(pan[x][y][0].second == 0)
            pan[x][y][0].second = 1;
        else if(pan[x][y][0].second == 1)
            pan[x][y][0].second = 0;
        else if(pan[x][y][0].second == 2)
            pan[x][y][0].second = 3;
        else if(pan[x][y][0].second == 3)
            pan[x][y][0].second = 2;

        d = pan[x][y][0].second;


        nx = x + dx[d];
        ny = y + dy[d];
        ncan = nxtcan(nx, ny);
        if(ncan == 0) {

            for(auto it: pan[x][y])
                pan[nx][ny].push_back(it);
            pan[x][y].clear();

            if(pan[nx][ny].size() >= 4)
                return true;
        }
        else if(ncan == 1) {
            reverse(pan[x][y].begin(), pan[x][y].end());
            for(auto it: pan[x][y])
                pan[nx][ny].push_back(it);
            pan[x][y].clear();

            if(pan[nx][ny].size() >= 4)
                return true;
        }
        else if(ncan == 2) {
            // do nothing
            return false;
        }
        else {return false;}
    }
    else {return false;}
    return false;
}
int solver(int time) {

    if(time > 1000)
        return -1;

    int chk;
    for(int k = 0; k < K; k++) {
        chk = 0;
        for(int i = 0 ; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(pan[i][j].size() > 0 && pan[i][j][0].first == k) {
                    if(mov(i, j))
                        return time;
                    chk = 1;
                    break;
                }
            }
            if(chk == 1)
                break;
        }
    }
    return solver(time+1);
}
int main() {

    //scanf("%d", &T);
    T = 1;
    for(int tc = 0; tc < T; tc++) {
        scanf("%d %d", &N, &K);
        table.clear();
        table.resize(N);
        pan.clear();
        pan.resize(N);

        for(int i = 0 ; i < N; i++) {
            table[i].resize(N);
            pan[i].resize(N);
            for(int j = 0; j < N; j++) {
                scanf("%d", &table[i][j]);
            }
        }
        for(int i = 0; i < K; i++) {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);

            pan[a-1][b-1].push_back(make_pair(i, c-1));

        }
        cout << solver(1) << endl;
    }
    return 0;
}

D. 결과