https://www.acmicpc.net/problem/17780
17780번: 새로운 게임
재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다. 게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽
www.acmicpc.net
17837번 새로운 게임 2 문제(문제 링크)와 거의 똑같은데 조금 더 쉬운 시뮬레이션 문제이다.
이 문제에서는 말이 맨 밑에 있지 않으면 이동시킬 수 없다는 것이 17837번 문제와의 차이점이다.
말의 정보는 구조체를 만들어서 행과 열의 위치, 방향을 넣어서 벡터에 저장한다.
벡터의 i번째 위치에는 i번째 말의 위치와 방향이 저장되어 있다.
방향 정보는 문제에서 알려준 순서대로 오른쪽, 왼쪽, 위쪽, 아래쪽이 각각 1, 2, 3, 4번의 인덱스가 되도록 배열에 넣어놓는다. 1번부터 시작하기 위해서 0번 위치에는 그냥 0을 넣어놨다.
말을 이동시키기 위해서는 deque배열을 사용하였다.
deque<int> dq[13][13];
위와 같이 deque<int>를 타입으로 가지는 2차원 배열이다.
dp[x][y]에는 x행 y열 위치에 있는 말들이 순서대로 저장되어 있다.
이제 턴을 진행하면서 4개 이상이 쌓이는 경우가 있다면 바로 게임을 종료하고 턴 수를 리턴한다.
문제 조건에 따라 1,000보다 크거나 절대로 게임이 종료되지 않는 경우에는 -1을 출력하기 위해서 -1을 리턴한다.
각 턴에서는 1번 말부터 k번말까지 순차적으로 이동시킨다.
문제 조건에 따라 이동시키기 전에 현재 이동시킬 말이 맨 밑에 있지 않다면 이동할 수 없으므로 바로 리턴한다.
이동시킬 말이 맨 밑에 있다면 이동할 칸의 색깔에 따라서 이동하게 된다.
이동할 칸이
- 범위를 벗어나거나 파란색 칸인 경우
- 원래 좌표에서 방향을 반대로 바꾼다.
- 다시 한 칸을 이동할 건데 이동할 칸이 또 범위를 벗어나거나 파란색일 경우 문제 조건에 따라 방향만 바꾼 채로 더 이동하지 않는다.
- 그렇지 않다면 이동을 한 건데 이동할 칸이 흰색이냐 빨간색이냐에 따라 다르게 이동할 것이므로 아래 조건들(밑에 2번, 3번 조건)을 이어서 실행해주면 된다.
- 원래 좌표에서 방향을 반대로 바꾼다.
- 흰색인 경우
- 현재 위치에 있는 말들을 순서대로 (큐의 앞부분부터) 이동할 위치로 이동시킨다.
- 빨간색인 경우
- 현재 위치에 있는 말들을 반대 순서로(큐의 뒷부분부터) 이동할 위치로 이동시킨다.
이동을 매번 할 때마다이동한 칸에 쌓인 말이 4개 이상이 되었는지 확인하고
4개 이상이 되었다면 true를 리턴, 그렇지 않다면 false를 리턴한다.
|
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
|
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
int n, k;
int map[13][13];
//오, 왼, 위, 아래
int dx[] = { 0, 0,0,-1,1 };
int dy[] = { 0, 1,-1,0,0 };
deque<int> dq[13][13];
struct Horse {
int x;
int y;
int dir;
Horse(int a, int b, int c) {
x = a;
y = b;
dir = c;
}
};
//말의 정보를 저장할 벡터
vector<Horse> vt;
bool move(int num) {
//num번호 말의 좌표와 방향
int x = vt[num].x;
int y = vt[num].y;
int dir = vt[num].dir;
int nx, ny, tmp;
//이동할 좌표
nx = x + dx[dir];
ny = y + dy[dir];
//말이 맨 밑에 있지 않으면 이동할 수 없다.
if (dq[x][y].front() != num) return false;
//이동할 좌표가 파란색이거나 범위를 벗어나는 경우
if (nx < 1 || ny < 1 || nx > n || ny > n || map[nx][ny] == 2) {
if (dir == 1 || dir == 3) dir++;
else dir--;
//반대로 다시 한칸 이동
nx = x + dx[dir];
ny = y + dy[dir];
//말의 방향 정보 업데이트
vt[num].dir = dir;
//다시 이동한 칸이 또 파란색이거나 범위를 벗어나면 방향만 바꾼채로 리턴
if (nx < 1 || ny < 1 || nx > n || ny > n || map[nx][ny] == 2) {
return false;
}
//그렇지 않다면 아래의 남은 코드 진행
}
//이동할 칸이 흰색인 경우
if (map[nx][ny] == 0) {
//현재 칸에 있는 말들을 순서대로 이동할칸으로 옮겨준다.
while (!dq[x][y].empty()) {
tmp = dq[x][y].front();
dq[x][y].pop_front();
dq[nx][ny].push_back(tmp);
vt[tmp].x = nx;
vt[tmp].y = ny;
}
}
else if (map[nx][ny] == 1) {
//이동할 칸이 빨간색인 경우
//현재 칸에 있는 말들을 뒤쪽부터 순서대로 이동할 칸으로 옮겨준다.
while (!dq[x][y].empty()) {
tmp = dq[x][y].back();
dq[x][y].pop_back();
dq[nx][ny].push_back(tmp);
vt[tmp].x = nx;
vt[tmp].y = ny;
}
}
//말이 4개 이상 쌓이면 true를 리턴
if (dq[nx][ny].size() >= 4) return true;
else return false;
}
int turnStart() {
int turnCnt = 1;
while (turnCnt <= 1000) {
bool flag = false;
for (int i = 1; i <= k; i++) {
flag = move(i);
//말이 4개이상 쌓여서 true값을 리턴받았다면 게임 종료(턴 수를 리턴)
if (flag) return turnCnt;
}
turnCnt++;
}
//1000번이 넘으면 -1을 리턴
return -1;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie();
cin >> n >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> map[i][j];
}
}
//1번부터 사용하기 위해 0번째 위치에는 쓰레기값 넣어 놓는다.
vt.push_back(Horse(-1, -1, -1));
int x, y, d;
for (int i = 1; i <= k; i++) {
cin >> x >> y >> d;
//말의 정보를 벡터에 넣는다.
vt.push_back(Horse(x, y, d));
//말이 있는 좌표에 말의 번호를 넣는다.
dq[x][y].push_back(i);
}
cout << turnStart() << '\n';
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 4179. 불! (0) | 2020.02.17 |
|---|---|
| [BOJ] 1938. 통나무 옮기기 (0) | 2020.02.12 |
| [BOJ] 17837. 새로운 게임 2 (0) | 2020.02.03 |
| [BOJ] 1600. 말이 되고픈 원숭이 (0) | 2020.02.01 |
| [BOJ] 2532. 반도체 설계 (0) | 2020.01.29 |
