BOJ(Java)
자바(백준) 3190 뱀
자바생
2021. 11. 24. 03:03
728x90
오답 노트 & 새로 알게 된 점
뱀 문제를 읽자마자 Deque가 떠올랐다.
시뮬레이션은 문제를 정말 잘 읽고 요약하는 습관이 필요한 것 같다.
요약하면서 어떻게 구현하면 좋을지 생각을 같이 하는 연습이 필요하다.
문제는 아래와 같이 정리하면 된다.
끝날 경우 2번을 보면 자기 자신과 몸이 부딪힐 경우이다.
이 때는 현재 머리를 놓은 위치를 dq의 element들과 비교해주면 된다.
order 배열은 시간에 따라 방향이 바뀌는 값을 저장한다.
D는 +1, L은 -1로 생각하여 order 배열에 넣어준다.
방향은 아래의 사진과 같이 생각하면 된다.
사진과 맞춰 dx, dy 배열도 방향 설정을 해주어야한다.
코드
|
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
|
import java.io.*;
import java.util.*;
public class Main {
static int atoi(String str) {
return Integer.parseInt(str);
}
static int N, K, L, ans;
static int dx[] = {0, 1, 0, -1};
static int dy[] = {1, 0, -1, 0};
//->방향이 0부터 시계방향으로 1, 2, 3
static boolean apple[][];
static int order[];
public static void main(String[] args) throws IOException {
input();
pro();
System.out.println(ans+1);
}
static void pro() {
Deque<Info> dq = new ArrayDeque<>();
dq.offer(new Info(0, 0, 0));
while (!dq.isEmpty()) {
Info info = dq.peekFirst();
if(order[ans] == 1){
info.status = (info.status + 1) % 4;
}
else if(order[ans] == -1){
info.status = (info.status - 1 + 4) % 4;
}
int nextX = info.x + dx[info.status];
int nextY = info.y + dy[info.status];
if(!isRangeTrue(nextX, nextY)) return;
if(isContain(dq, nextX, nextY)) return;
dq.offerFirst(new Info(nextX, nextY, info.status));
ans++;
if(apple[nextX][nextY]){
apple[nextX][nextY] = false;
}
else{
dq.pollLast();
}
}
}
static boolean isContain(Deque<Info> dq, int x, int y) {
for (Info info : dq) {
if(info.x == x && info.y == y) return true;
}
return false;
}
static boolean isRangeTrue(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < N;
}
static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = atoi(br.readLine());
K = atoi(br.readLine());
apple = new boolean[N][N];
for (int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine());
int x = atoi(st.nextToken());
int y = atoi(st.nextToken());
apple[x-1][y-1] = true;
//문제에서 1,1 부터 시작한다
//나는 0,0 부터 시작이기 때문에 사과의 좌표를 하나씩 땅겨줘야한다.
}
L = atoi(br.readLine());
order = new int[10001];
for (int i = 0; i < L; i++) {
st = new StringTokenizer(br.readLine());
int time = atoi(st.nextToken());
String dir = st.nextToken();
switch (dir){
case "D":
order[time] = 1;
break;
case "L":
order[time] = -1;
break;
}
}
}
static class Info{
int x, y, status;
public Info(int x, int y, int status) {
this.x = x;
this.y = y;
this.status = status;
}
}
}
|
cs |
728x90