728x90
https://www.acmicpc.net/problem/3190
3190번: 뱀
문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따
www.acmicpc.net
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
|
/*
-------------------------------------------------------------------------------------------------------------
(1) 사과 먹으면 늘어난다.
(2) 벽 또는 자기자신의 몸과 부딪히면 게임 끝.
(3) 보드의 상하좌우 끝에 벽이 있다. 뱀 길이 : 1, 위치 (0, 0)
(4) 뱀은 처음 오른쪽을 향한다
- 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
- 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
- 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸 길이는 변하지 않는다.
결과: 사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.
------------------------------------------------------------------------------------------------------------
입력
첫줄 : 보드 크기 N (2 <= N <=100)
사과의 개수 K (0 <= k <= 100)
사과의 위치 ( 행, 열)
뱀의 방향 변환 횟수 L
뱀의 방향 전환 정보 (정수 X, 문자 C ( L 왼쪽 90도 회전, D 오른쪽 90도 회전 ))
-------------------------------------------------------------------------------------------------------------
문제 해결 방안:
중요한 점: 꼬리가 길어지는게 아니라 멀이가 길어진다고 생각해라!!!!
1. 정수형 배열에 맵의 정보를 받는다.
2. 구조체 큐에 시간과 방향을 받는다.
(1) 방향과 시간 정보 받을 구조체 int, char
(2) 뱀의 자리 정보를 받을 구조체 int, int
3. 완전탐색
(1) sec ++ 하면서 큐 프론트 값이 가진 시간과 현재 시간이 같을 때 방향 전환 실시
(2) 아닐경우 계속 직진한다.
- 벽에 부딪히면 게임 종료 ( sec 출력)
- 자기 자신과 부딪혀도 게임 종료
(3) 사과가 아닐경우 큐 pop() , 꼬리부분 false 처리;
(4) 사과일 경우 true 처리
(5) 방향처리
- dir 이 'L' 이면 idx--
- dir 이 'R' 이면 idx++
*/
#include <iostream>
#include <vector>
#include <queue>
#define MAX 100
using namespace std;
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};
int N, K, L;
bool visited[MAX][MAX];
bool apple[MAX][MAX];
struct p
{
int t;
char dir;
};
struct s
{
int y;
int x;
};
queue<p> DirInfo;
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> K;
for (int k = 0; k < K; k++)
{
int y, x;
cin >> y >> x;
apple[y - 1][x - 1] = true; // 사과 위치 true 처리
}
cin >> L;
for (int l = 0; l < L; l++) //시간, 방향에 대한 정보를 담는다.
{
int X;
char C;
cin >> X >> C;
DirInfo.push({X, C});
}
int sec = 0;
int idx = 0; //초기 오른쪽
queue<s> snake;
visited[0][0] = true; //방문 처리
while (1)
{
sec++; //시간 ++
s cur = {before.y + dy[idx], before.x + dx[idx]}; // 전 + 방향 값은 다음에 갈 자리
//뱀의 머리가 몸에 부딪히거나, 범위를 벗어날 경우
if (visited[cur.y][cur.x] || (cur.y < 0 || cur.y >= N || cur.x < 0 || cur.x >= N))
{
cout << sec << "\n";
break;
}
visited[cur.y][cur.x] = true;
//사과가 있는 위치면 꼬리 그대로
if (apple[cur.y][cur.x])
apple[cur.y][cur.x] = false;
//사과 없으면 꼬리가 있던 칸을 지운다
else
{
s tail = snake.front();
visited[tail.y][tail.x] = false;
snake.pop();
}
//마지막에 방향 전환
if (DirInfo.size() && DirInfo.front().t == sec)
{
if (DirInfo.front().dir == 'L')
{
idx--;
if (idx == -1)
idx = 3;
}
else
{
idx++;
if (idx == 4)
idx = 0;
}
DirInfo.pop(); //꼬리
}
}
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
728x90
'Algorithm Study > BOJ with C++' 카테고리의 다른 글
(BAEKJOON) 14891번: 톱니바퀴 (0) | 2020.04.20 |
---|---|
(BAEKJOON) 13458번: 시험 감독 (0) | 2020.04.18 |
(BAEKJOON) 14499번: 주사위 굴리기 (0) | 2020.04.17 |
(BAEKJOON) 14500번: 테트로미노 (0) | 2020.04.17 |
(BAEKJOON) 12100번: 2048(Easy) (0) | 2020.04.16 |
댓글