17144번: 미세먼지 안녕!
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사
www.acmicpc.net
💡풀이💡
문제에 적힌 조건들에서 알 수 있는 정보
확산
1. 확산되는 양은 Ar,c/5 이기 때문에 미세먼지 양이 5미만은 0이 확산된다 >> 미세먼지 양이 5이상인 것만 체크!
2. 확산은 동시에 일어나기 때문에 한 곳에서 확산이 일어나면 확산이 일어나야 하는 다른 쪽에서는 미세먼지 양이 기존과 달라질 수 있음 >> 확산이 일어나기 전 각 미세먼지 위치와 양을 저장하는 것이 필요!
공기 청정기
1. 공기청정기는 위와 아래가 나눠져 있음 >> 위쪽 위치와 아래쪽 위치를 저장
2. 바람이 순환할 때 공기청정기의 값이 순환 방향에 따라 이동하지 않도록 조치하기
1. 입력 받기
미세먼저 정보를 저장할 때, 미세먼지를 확인한 순서대로 꺼내기 위해서 ArrayDeque을 이용해 큐처럼 사용했다.
큐에 저장할 정보는 미세먼지 있는 칸의 i, j 좌표와 미세먼지 양이기 때문에 int[] 타입으로 선언했다.
static int[] dr = { 0, -1, 0, 1 }; // 우상좌하
static int[] dc = { 1, 0, -1, 0 }; // 우상좌하
static int[][] room;
static int R, C;
static int airUp, airDown;
static ArrayDeque<int[]> q;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken()); // 행 길이
C = Integer.parseInt(st.nextToken()); // 열 길이
int T = Integer.parseInt(st.nextToken()); // 초
airUp = 0; // 공기청정기 위쪽 위치
airDown = 0; // 공기 청정기 아래쪽 위치
q = new ArrayDeque<>(); // 미세먼지 정보 저장
room = new int[R][C]; // 방 정보 저장
for (int i = 0; i < R; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < C; j++) {
room[i][j] = Integer.parseInt(st.nextToken());
if (room[i][j] == -1 && airUp == 0) {
airUp = i;
airDown = i + 1;
}
}
}
}
2. 미세먼지 있는 곳 체크
위에서 찾은 것처럼 확산되는 양은 Ar,c/5 이기 때문에 미세먼지 양이 5미만은 0이 확산되기 때문에 큐에 추가하지 않아 계산 해야 하는 양을 줄인다.
static void checkDust() {
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (room[i][j] < 5) continue;
q.offer(new int[] { i, j, room[i][j] }); // 행 위치, 열 위치, 미세먼지 양
}
}
}
3. 확산 시키기
1) 미세먼지를 저장한 큐에 원소가 없을 때까지 반복
2) 큐에 저장된 정보를 꺼내서 그 좌표를 중심으로 4방향 탐색
3) 배열의 범위 안이고, 공기청정기 위치가 아니면 확산 시키기
4) 4방향 탐색이 끝나고 확산된 갯수만큼 현재 위치에 남은 미세먼지 양 구하기
static void spread() {
while (!q.isEmpty()) {
int[] val = q.poll();
int cnt = 0; // 확산된 방향 개수
int spreadDust = val[2]/5; // 확산되는 미세먼지 양
for (int d = 0; d < 4; d++) { // 4방향 탐색
int ni = val[0] + dr[d];
int nj = val[1] + dc[d];
//배열 범위 안이고 공기청정기 위치가 아니면
if (0 <= ni && ni < R && 0 <= nj && nj < C && room[ni][nj] != -1) {
cnt++;
room[ni][nj] += spreadDust; // 확산된 위치에 확산된 미세먼지 양 더하기
}
}
room[val[0]][val[1]] -= spreadDust * cnt; // 남은 미세먼지 양 계산
}
}
4. 공기청정기 작동
배열의 원소를 이동시킬 때, 이동 과정에서 유실되는 값이 없게 해야한다! 그러기 위해서
공기청정기에서부터 나오는 방향 > 공기청정기로 들어가는 방향 으로 이동한게 아니라 반대로
공기청정기에서 들어가는 방향 > 공기청정기에서 나오는 방향 으로 배열을 순환시켰다.
공기청정기는 이동하지 않는다. 그렇기 때문에 공기청정기에서 나오는 방향에 있는 원소들은 이동 후에 원래 자리에 새로운 원소가 이동해 오지 않아서 그대로 값이 남아있게 된다. 그래서 이동 후에 그 부분의 값이 0이 되도록 했다.
static void airClean() {
// 위쪽 공기 회전
for (int i = airUp - 1; i > 0; i--) { // V
room[i][0] = room[i - 1][0];
}
for (int i = 1; i < C; i++) { // <
room[0][i - 1] = room[0][i];
}
for (int i = 1; i <= airUp; i++) { // ^
room[i - 1][C - 1] = room[i][C - 1];
}
for (int i = C - 1; i > 0; i--) { // >
if(i==1) room[airUp][i] = 0;
else room[airUp][i] = room[airUp][i - 1];
}
// 아래쪽 공기 회전
for (int i = airDown + 2; i <= R - 1; i++) { // ^
room[i - 1][0] = room[i][0];
}
for (int i = 1; i < C; i++) { // <
room[R - 1][i - 1] = room[R - 1][i];
}
for (int i = R - 1; i > airDown; i--) { // V
room[i][C - 1] = room[i - 1][C - 1];
}
for (int i = C - 1; i > 0; i--) { // >
if(i==1) room[airDown][i] = 0;
else room[airDown][i] = room[airDown][i - 1];
}
}
5. T 초만큼 작동 후 남은 미세먼지 양 구하기
int sec = 0;
while (sec < T) {
// 미세먼지 있는 곳 체크
checkDust();
// 미세먼지 확산
spread();
// 공기청정기 작동
airClean();
sec++;
}
int sum = 0;
for (int[] r : room) {
for (int val : r)
sum += val;
}
System.out.println(sum + 2);
6. 전체 코드
package backjoon;
import java.io.*;
import java.util.*;
public class B17144 {
static int[] dr = { 0, -1, 0, 1 }; // 우상좌하
static int[] dc = { 1, 0, -1, 0 }; // 우상좌하
static int[][] room;
static int R, C;
static int airUp, airDown;
static ArrayDeque<int[]> q;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken()); // 행 길이
C = Integer.parseInt(st.nextToken()); // 열 길이
int T = Integer.parseInt(st.nextToken()); // 초
airUp = 0; // 공기청정기 위쪽 위치
airDown = 0; // 공기 청정기 아래쪽 위치
q = new ArrayDeque<>(); // 미세먼지 정보 저장
room = new int[R][C]; // 방 정보 저장
for (int i = 0; i < R; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < C; j++) {
room[i][j] = Integer.parseInt(st.nextToken());
if (room[i][j] == -1 && airUp == 0) {
airUp = i;
airDown = i + 1;
}
}
}
int sec = 0;
while (sec < T) {
// 미세먼지 있는 곳 체크
checkDust();
// 미세먼지 확산
spread();
// 공기청정기 작동
airClean();
sec++;
}
int sum = 0;
for (int[] r : room) {
for (int val : r)
sum += val;
}
System.out.println(sum + 2);
}
static void checkDust() {
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (room[i][j] < 5) continue;
q.offer(new int[] { i, j, room[i][j] }); // r, c, 미세먼지 양
}
}
}
static void spread() {
while (!q.isEmpty()) {
int[] val = q.poll();
int cnt = 0; // 확산된 방향 개수
int spreadDust = val[2]/5;
for (int d = 0; d < 4; d++) {
int ni = val[0] + dr[d];
int nj = val[1] + dc[d];
if (0 <= ni && ni < R && 0 <= nj && nj < C && room[ni][nj] != -1) {
cnt++;
room[ni][nj] += spreadDust;
}
}
room[val[0]][val[1]] -= spreadDust * cnt;
}
}
static void airClean() {
// 위쪽 공기 회전
for (int i = airUp - 1; i > 0; i--) { // V
room[i][0] = room[i - 1][0];
}
for (int i = 1; i < C; i++) { // <
room[0][i - 1] = room[0][i];
}
for (int i = 1; i <= airUp; i++) { // ^
room[i - 1][C - 1] = room[i][C - 1];
}
for (int i = C - 1; i > 0; i--) { // >
if(i==1) room[airUp][i] = 0;
else room[airUp][i] = room[airUp][i - 1];
}
// 아래쪽 공기 회전
for (int i = airDown + 2; i <= R - 1; i++) { // ^
room[i - 1][0] = room[i][0];
}
for (int i = 1; i < C; i++) { // <
room[R - 1][i - 1] = room[R - 1][i];
}
for (int i = R - 1; i > airDown; i--) { // V
room[i][C - 1] = room[i - 1][C - 1];
}
for (int i = C - 1; i > 0; i--) { // >
if(i==1) room[airDown][i] = 0;
else room[airDown][i] = room[airDown][i - 1];
}
}
}'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
| [백준 2563] 색종이 (0) | 2023.02.15 |
|---|---|
| [백준 15685] 드래곤 커브 (0) | 2023.02.15 |
| [백준 1158] 요세푸스 문제 (0) | 2023.02.13 |
| [백준 1012] 유기농 배추 (0) | 2023.02.12 |
| [백준 2164] 카드2 (0) | 2023.02.10 |
댓글