Algorithm/백준

[BOJ] - 3190. 뱀

benguin 2019. 8. 5. 18:00

[URL]

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

 

3190번: 뱀

문제  'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따

www.acmicpc.net

[풀이 과정]

* 시뮬레이션

뱀의 머리랑 꼬리에만 신경 쓰자

뱀의 전체는 check[][]배열에 넣어주자. : 이동 가능한지 판단

 

1) input()

int rota[10001]; // 1: L 왼쪽 90회전, 2: R 오른쪽 90회전 , 0이면 회전X

2) while(1)

sec증가, 뱀의 머리가 갈 수 있는지 판단, 

가능하면 move(), 불가능하면 break;

 

move()

1. 사과가 있는 경우

// 사이즈 증가 

// 뱀 머리 벡터에 저장 

// 뱀 현재 위치 판단 

// 먹은 사과 지워주고 
// 뱀 머리 이동 

 

2. 사과가 없는 경우

// 뱀 머리 벡터에 저장
// 뱀 현재 위치 판단
// 뱀 꼬리쪽 이동, 현재 위치 판단
// 꼬리 벡터에서 지워주기
// 뱀 머리 이동

[소스 코드]

 

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
158
159
160
161
162
#include <stdio.h>
#include <vector>
using namespace std;
 
struct Snake {
    int x = 1;
    int y = 1;
    int dir = 3;        // 오른쪽 방향 시작
    int size = 1;
};
Snake s1;
vector <pair <intint>> v;
 
 
int N;
int K;
int L;
int map[101][101];
bool check[101][101];
 
int rota[10001];        // 1: L 왼쪽 90회전, 2: R 오른쪽 90회전
 
int dx[] = { -1100 };        // 0상 1하 2좌 3우 
int dy[] = { 00-11 };
 
void input() {
    scanf("%d"&N);
    scanf("%d"&K);
 
    for (int i = 0; i < K; i++)
    {
        int x, y;
        scanf("%d"&x);
        scanf("%d"&y);
 
        map[x][y] = 1;
    }
    scanf("%d\n"&L);
 
    for (int i = 0; i < L; i++)
    {
        int tempX;
        char tempC;
 
        scanf("%d %c"&tempX, &tempC);
 
        if (tempC == 'L')
        {
            rota[tempX] = 1;
        }
        if (tempC == 'D')
        {
            rota[tempX] = 2;
        }
    }
 
    check[1][1= true;        // 맨 처음 뱀의 위치 설정
    v.push_back(make_pair(11));        // 맨 처음 뱀의 위치 벡터에 저장
}
 
bool isPossible() {
    bool flag = false;
    
    int nx = s1.x + dx[s1.dir];
    int ny = s1.y + dy[s1.dir];
 
 
    if (nx >= 1 && nx <= N && ny >=1 && ny <= N)
    {
        if (check[nx][ny] == false)
        {
            flag = true;
        }
    }
 
    return flag;
}
 
void move() {
    int nx = s1.x + dx[s1.dir];
    int ny = s1.y + dy[s1.dir];
 
    if (map[nx][ny] == 1)        // 다음 뱀 헤드가 사과인 경우
    {
        s1.size++;        // 사이즈 증가
        v.push_back(make_pair(nx, ny));    // 뱀 머리 벡터에 저장
        check[nx][ny] = true;        // 뱀 현재 위치 판단
 
        map[nx][ny] = 0;        // 먹은 사과 지워주고
        s1.x = nx;        // 뱀 머리 이동
        s1.y = ny;
    }
    else                        // 다음 뱀 헤드가 사과가 아닌 경우
    {
        v.push_back(make_pair(nx, ny));        // 뱀 머리 벡터에 저장
        check[nx][ny] = true;        // 뱀 현재 위치 판단
 
        check[v[0].first][v[0].second] = false;        // 뱀 꼬리쪽 이동, 현재 위치 판단
        v.erase(v.begin());        // 꼬리 벡터에서 지워주기
        s1.x = nx;        // 뱀 머리 이동
        s1.y = ny;
    }
}
 
 
int main() {
    input();
 
    int sec = 0;
    while (true)
    {
        sec++;
 
        if (isPossible())        // 벽 아니고 본인 아닐 때 가능!
        {
            move();        // 가능하면 이동!
        }
        else
        {
            break;                // 아닐 경우 이동 불가 탈출
        }
 
        // 해당 초에 회전 
        if (rota[sec] != 0)
        {
            if (rota[sec] == 1)
            {
                if (s1.dir == 0) { 
                    s1.dir = 2;
                }
                else if (s1.dir == 1) {
                    s1.dir = 3;
                }
                else if (s1.dir == 2) {
                    s1.dir = 1;
                }
                else if (s1.dir == 3) {
                    s1.dir = 0;
                }
            }
            else if (rota[sec] == 2)
            {
                if (s1.dir == 0) {
                    s1.dir = 3;
                }
                else if (s1.dir == 1) {
                    s1.dir = 2;
                }
                else if (s1.dir == 2) {
                    s1.dir = 0;
                }
                else if (s1.dir == 3) {
                    s1.dir = 1;
                }
            }     
        }
    }
 
    printf("%d\n", sec);
 
    return 0;
}
cs

'Algorithm > 백준' 카테고리의 다른 글

[BOJ] - 2468. 안전 영역  (0) 2019.08.20
[BOJ] - 17281. 야구  (0) 2019.08.13
[BOJ] - 17143. 낚시왕  (0) 2019.07.31
17140. - 이차원 배열과 연산  (0) 2019.07.16
[BOJ] - 16236. 아기 상어  (0) 2019.07.10