백준 17837 새로운 게임 2

작성일 | In |

Problem : 새로운 게임 2

유형 : 구현

문재 해석

  • 규칙에 맞춰서 말을 움직이고, 게임이 종료되는 턴을 구한다.
  • 턴이 1000회를 넘을경우 -1를 출력한다.

문제 재해석

  • 단순 구현 문제이다.

해결 전략

  • N과 K가 적으므로 시키는 대로 구현을 하면 된다.

image

  • 말 위에 점차 쌓여 가므로, 스택을 이용했다.
  • 좌표마다 스택을 두고, 해당 좌표에 어떤 말이 있는지 쌓아 올렸다.

설계, 구현

  • K번 말의 위치와 방향을 보관 한다.
  • K번 말을 움직일 때, K 위에 무슨 말들이 있는지 확인한다.
  • 빨간색인 경우 뒤집는다.
  • reverse 함수를 쓰기 위해 임시로 담는 공간은 deque를 이용했다.

주의할 점

  • 시작하자마자 게임이 끝날 수 있다.
  • 턴이 진행되던 중에 말이 4개 이상 쌓이는 순간 이라는 조건 떄문인지 위 조건을 처리해주지 않아도 통과함.
  • 입력으로 들어오는 좌표는 0이 아니라 1부터 시작이다.
  • 명령에 따른 방향 좌표는 시계 방향이 아니다. 재 설정이 필요하다.



파랑빨강파랑

  • 현재 말의 위치가 빨강이고, 방향 양쪽 다 파란색인 경우가 있을 수 있다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <bits/stdc++.h>
using namespace std;

struct st {
    int x;
    int y;
    int dir;
};

int n, k;
int nx, ny;
int board[14][14];
const int White = 0, Red = 1, Blue = 2;

const int dx[] = { -1,0,1,0 };
const int dy[] = { 0,1,0,-1 };

stack<int> board_stack[14][14];
st status[12];
deque<int> tmp;

void push_new_spot(st cur) {

    if (nx < 0 or nx >= n or ny < 0 or ny >= n or board[nx][ny] == Blue) {
        nx = cur.x;
        ny = cur.y;
    }
    else if (board[nx][ny] == Red) reverse(tmp.begin(), tmp.end());

    while (!tmp.empty()) {
        int curr = tmp.front(); tmp.pop_front();
        status[curr].x = nx;
        status[curr].y = ny;
        board_stack[nx][ny].push(curr);
    }
}

void range_or_Blue_check(st& cur) {

    if (nx < 0 or nx >= n or ny < 0 or ny >= n or board[nx][ny] == Blue) {

        cur.dir = (cur.dir + 2) % 4;

        nx = cur.x + dx[cur.dir];
        ny = cur.y + dy[cur.dir];
    }
}

bool Init_check() {
    for (int i = 1; i <= k; ++i) {
        auto cur = status[i];
        if (board_stack[cur.x][cur.y].size() >= 4) return true;
    }
    return false;
}

int solve() {

    int cnt = 0;

    if (Init_check()) return 0;

    while (1) {
        cnt++;
        if (cnt > 1000) return -1;

        for (int i = 1; i <= k; ++i) {
            auto cur = status[i];

            while (1) {
                int TOP = board_stack[cur.x][cur.y].top();    board_stack[cur.x][cur.y].pop();
                tmp.push_front(TOP);
                if (TOP == i) break;
            }

            nx = cur.x + dx[cur.dir];
            ny = cur.y + dy[cur.dir];

            range_or_Blue_check(cur);
            push_new_spot(cur);

            status[i].x = nx;
            status[i].y = ny;
            status[i].dir = cur.dir;


            if (board_stack[nx][ny].size() >= 4) return cnt;
        }

    }

    return -1;
}

void input() {
    cin >> n >> k;

    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < n; ++ii) {
            cin >> board[i][ii];
        }
    }

    int a, b, c;
    for (int i = 1; i <= k; ++i) {
        cin >> a >> b >> c;
        status[i].x = a - 1;
        status[i].y = b - 1;

        if (c == 1) status[i].dir = 1;
        else if (c == 2) status[i].dir = 3;
        else if (c == 3) status[i].dir = 0;
        else if (c == 4) status[i].dir = 2;

        board_stack[status[i].x][status[i].y].push(i);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    input();
    cout << solve() << "\n";

    return 0;
}

피드백

  • 문제 조건에서 놓친 부분이 많았다. (1부터 시작, 시계 방향이 아님)
  • 이로 인해, 구현 방향은 맞았으나, 디버깅에서 시간이 많이 소모되었다.
  • 구현하기 전에 완벽히 설계하고, 구현 전에 문제를 한번 더 읽어서 놓친 부분이 있는지 확인하자.