BOJ(Java)
자바(백준) 17144 미세먼지 안녕!
자바생
2021. 11. 23. 16:22
728x90
오답 노트 & 새로 알게 된 점
처음에 문제를 잘못 이해하여 엉뚱하게 풀었다.
1초마다 미세먼지 확산 후 공기청정기가 작동되는데,
나는 처음에 미세먼지 확산이 되고 T초동안 공기청정기를 돌렸다.
즉, 미세먼지 확산되고, 공기청정기 작동후에, 또 다시 미세먼지 확산되고 공기청정기를 돌려야한다.
전체적인 흐름은
미세먼지 큐에 넣기 -> 미세먼지 확산 -> 공기청정기 돌리기
이다.
A배열에서 양의 정수를 모두 큐에 넣어준다.
real 배열을 이용하여 미세먼지를 확산시킨다.
A배열로 미세먼지를 확산시킬 때, 중복으로 더해지는 값이 있을까봐 real 배열을 사용했다.
제일 중요한 rotate 메서드이다.
rotate메서드는 크게 공기청정기의 윗 부분, 아랫 부분으로 나눴다.
그리고 방향으로는 -->, <---. 위, 아래 부분으로 나눈다.
1번 방향
for (int i = 1; i < col; i++) {
rotate[air[0]][i] = real[air[0]][i - 1];
rotate[air[1]][i] = real[air[1]][i - 1];
}
2번 방향
for (int i = col - 1; i >= 1; i--) {
rotate[0][i - 1] = real[0][i];
rotate[row - 1][i - 1] = real[row - 1][i];
}3번 방향
for (int i = 0; i < row - 1; i++) {
if (i >= air[1]) {
rotate[i + 1][col - 1] = real[i][col - 1];
} else {
rotate[i + 1][0] = real[i][0];
if (i + 1 == air[0]) rotate[i + 1][0] = 0;
}
}배열을 첫 행부터 끝행까지 옮긴다고 생각했다.
그러면서 공기청정기의 윗 부분, 아랫 부분을 나누어 생각했다.
4번 방향
for (int i = air[0]; i >= 1; i--) {
rotate[i - 1][col - 1] = real[i][col - 1];
}5번 방향
for (int i = row - 1; i > air[1]; i--) {
rotate[i - 1][0] = real[i][0];
if (i - 1 == air[1]) rotate[i - 1][0] = 0;
}
spread할 때 공기청정기의 위치가 필요하기 때문에,
회전을 다 한뒤에 공기청정기 위치를 나타내준다.
rotate[air[0]][0] = -1;
rotate[air[1]][0] = -1;
rotate배열을 A배열에 복사해준다.
왜?
A의 미세먼지를 기준으로 큐에 넣어주기 때문이다.
위의 과정을 T초동안 반복한 뒤,
공기청정기를 제외한 A배열의 value들을 더해주면 된다.
문제를 처음에 잘못 읽어서 4~5시간 동안 문제를 풀게됐다..
앞으로 문제를 꼼꼼히 잘 읽어야겠다.
2021.11.29 복습
문제를 다시 풀어보았을 때 새로운 점을 하나 발견했다.
처음 풀었을 때는 rotate 배열에 real 배열의 index를 옮기면서 넣어주었다.
그래서 공기를 순환하는 방향에 상관없이 넣어도됐다.
이번에는 A배열 안에서 index를 움직여 공기 순환을 하려고 했다.
그러나 이와 같이 코드를 작성하면 공기 순환하는 방향을 고려해줘야한다.
왜냐하면 중복해서 밀려날 수도 있다.
오른쪽 6 6 6 을 보면 원래 답은 6 5 6이 되어야한다.
하지만 순서를 고려하지 않아
빨간색 부분이 먼저 옮겨 가게 되고, 5는 사라지면서 6 6 6 이 되버린다.
그래서 A배열 안에서 움직이려면 꼭 순서를 고려해줘야한다.
코드
|
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
|
package simulation;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
public class BOJ17144 {
static int atoi(String str) {
return Integer.parseInt(str);
}
static int row, col, T;
static int A[][]; //원래 입력된 배열
static int real[][]; //바뀌는 배열
static Queue<Integer> q; //미세먼지
static int dx[] = {-1, 1, 0, 0};
static int dy[] = {0, 0, 1, - 1};
static int air[];
static int rotate[][];
public static void main(String[] args) throws IOException {
input();
pro();
}
static void pro() {
while(T-- > 0) {
setQueue();
real = new int[row][col];
spreadDust();
rotate();
}
int sum = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if(A[i][j] == -1) continue;
sum += A[i][j];
}
}
System.out.println(sum);
}
static void spreadDust() {
while (!q.isEmpty()) {
int x = q.poll();
int y = q.poll();
int cnt = 0;
for (int i = 0; i < 4; i++) {
int X = x + dx[i];
int Y = y + dy[i];
if(!isRangeTrue(X,Y)) continue;
if(A[X][Y] == -1) continue;
real[X][Y] += A[x][y] / 5;
cnt++;
}
real[x][y] = real[x][y] + (A[x][y] - (A[x][y] / 5) * cnt);
}
}
static void setQueue() {
q = new ArrayDeque<>();
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if(A[i][j] > 0){
q.offer(i);
q.offer(j);
}
}
}
}
static void rotate() {
rotate = new int[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
rotate[i][j] = real[i][j];
}
}
//---> 방향
for (int i = 1; i < col; i++) {
rotate[air[0]][i] = real[air[0]][i - 1];
rotate[air[1]][i] = real[air[1]][i - 1];
}
// <---- 방향
for (int i = col - 1; i >= 1; i--) {
rotate[0][i - 1] = real[0][i];
rotate[row - 1][i - 1] = real[row - 1][i];
}
//아래 방향
for (int i = 0; i < row - 1; i++) {
if (i >= air[1]) {
rotate[i + 1][col - 1] = real[i][col - 1];
} else {
rotate[i + 1][0] = real[i][0];
if (i + 1 == air[0]) rotate[i + 1][0] = 0;
}
}
//공기청정기 윗부분 위 방향
for (int i = air[0]; i >= 1; i--) {
rotate[i - 1][col - 1] = real[i][col - 1];
}
//공기청정기 아랫부분 위방향으로
for (int i = row - 1; i > air[1]; i--) {
rotate[i - 1][0] = real[i][0];
if (i - 1 == air[1]) rotate[i - 1][0] = 0;
}
//공기청정기 위치 나타내기 --> spread할 때 필요함
rotate[air[0]][0] = -1;
rotate[air[1]][0] = -1;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
A[i][j] = rotate[i][j];
}
}
}
static boolean isRangeTrue(int x, int y) {
return x >= 0 && x < row && y >= 0 && y < col;
}
static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
row = atoi(st.nextToken());
col = atoi(st.nextToken());
T = atoi(st.nextToken());
A = new int[row][col];
air = new int[row];
int idx = 0;
for (int i = 0; i < row; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < col; j++) {
A[i][j] = atoi(st.nextToken());
if(A[i][j] == -1){
air[idx] = i;
idx++;
}
}
}
}
}
|
cs |
728x90