https://www.acmicpc.net/problem/17144
17144번: 미세먼지 안녕!
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사
www.acmicpc.net
문제 설명
예제 입력 1 복사
7 8 1
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0
예제 출력 1 복사
188
예제 입력 2 복사
7 8 2
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0
예제 출력 2 복사
188
예제 입력 3 복사
7 8 3
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0
예제 출력 3 복사
186
예제 입력 4 복사
7 8 4
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0
예제 출력 4 복사
178
예제 입력 5 복사
7 8 5
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0
예제 출력 5 복사
172
예제 입력 6 복사
7 8 20
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0
예제 출력 6 복사
71
예제 입력 7 복사
7 8 30
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0
예제 출력 7 복사
52
예제 입력 8 복사
7 8 50
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0
예제 출력 8 복사
46
문제 해석
공기청정기
공기 청정기의 위치 : 1열에 행을 2칸 차지한 형태, -1로 구분되어 있다.
공기청정기의 공기 흐름은 윗방향과, 아랫방향이 다르다.
윗방향 : 반시계방향
아랫방향 : 시계방향
공기청정기의 방향 흐름에 따라 미세먼지가 한 칸씩 이동되고 공기청정기로 들어간 미세먼지는 모두 정화된다.
미세먼지의 확산
미세먼지의 양이 5에 배수로 확산되므로 미세먼지 양이 5보다 작을 때는 확산이 안된다.
6 | 8 | |
6 8 로 미세먼지가 붙어있을 때 확산은 동시에 일어나고 확산되기 전 미세먼지 양의 /5 씩 확산시켜야함
즉
6 입장 > 6 / 5 = 1 씩 2칸에 확산됨
8 입장 > 8/ 5 = 1 씩 3칸에 확산됨
이것이 동시에 일어나게 된다.
6 - 1*2 + 1 | 8 - 1*3 +1 | +1 |
+1 | +1 | |
공기청정기를 구동 시킨 이후 T초가 지난 후 방에 있는 미세먼지 양을 출력한다.
* 구현 로직 *
1. 미세 먼지가 확산하는 것
2. 공기청정기로 미세먼지를 처리하는 것
두가지를 나눠서 생각해야한다.
간단한 로직이지만 나눠서 코드를 짜야한다는 생각이 안들고 한꺼번에 짜야한다는 의무감만 들어서 나에겐 너무 어려웠던 문제였다.
많은 풀이 중에 제일 이해가 잘되는 코드를 사용했다 :)
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
public class Main {
static int R, C, T;
static int[][] map;
static int[] up = {1, -1, 0, 0}, side = {0, 0, 1, -1};
static int airPos1, airPos2;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
R = Integer.parseInt(s[0]);
C = Integer.parseInt(s[1]);
T = Integer.parseInt(s[2]);
map = new int[R][C];
int num = 0;
for (int i = 0; i < R; i++) {
String[] s1 = br.readLine().split(" ");
for (int j = 0; j < C; j++) {
map[i][j] = Integer.parseInt(s1[j]);
}
}
findAir(); // 공기청정기 위치를 찾아 airPos1, airPos2에 넣어줍니다.
for (int i = 0; i < T; i++) {
solve();
}
int result = count(); // map의 배열 남아있는 먼지의 양을 계산해줍니다.
System.out.println(result + 2); // count()에서 공기청정기 값인 -1을 2번 더했으므로 2를 더해줍니다.
}
public static void findAir() {
for (int i = 0; i < R; i++) {
if (map[i][0] == -1) {
airPos1 = i;
airPos2 = i + 1;
break;
}
}
}
public static void solve() {
map=dustSimulation(); // 먼지가 퍼져나가는 것을 구하는 함수
airSimulation(); // 공기청정기로 먼지가 들어오며 나가는 것을 구하는 함수
}
public static void airSimulation() {
int top = airPos1; // 공기청정기 윗 부분좌표며, 반시계 방향으로 진행
for (int x = top - 1; x > 0; x--) {
map[x][0] = map[x - 1][0];
}
for (int y = 0; y < C - 1; y++) {
map[0][y] = map[0][y + 1];
}
for (int x = 0; x < top; x++) {
map[x][C - 1] = map[x + 1][C - 1];
}
for (int y = C - 1; y > 1; y--) {
map[top][y] = map[top][y - 1];
}
map[top][1] = 0; // 공기청정기로 나가는 곳이므로 먼지는 0이다.
int bottom = airPos2; // 공기청정기 밑 부분좌표며, 시계방향으로 진행
for (int x = bottom + 1; x < R - 1; x++) {
map[x][0] = map[x + 1][0];
}
for (int y = 0; y < C - 1; y++) {
map[R - 1][y] = map[R - 1][y + 1];
}
for (int x = R - 1; x > bottom; x--) {
map[x][C - 1] = map[x - 1][C - 1];
}
for (int y = C - 1; y > 1; y--) {
map[bottom][y] = map[bottom][y - 1];
}
map[bottom][1] = 0; // 공기청정기로 나가는 곳이므로 먼지는 0이다.
}
public static int[][] dustSimulation() {
int[][] tMap = new int[50][50];
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (map[i][j] == -1) {
tMap[i][j] = -1;
continue;
}
tMap[i][j] += map[i][j];
for (int k = 0; k < 4; k++) {
int nx = j + side[k];
int ny = i + up[k];
if (ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
if (map[ny][nx] == -1) continue;
tMap[ny][nx] += (map[i][j] / 5);
tMap[i][j] -= (map[i][j] / 5);
}
}
}
return tMap;
}
public static int count() {
int temp = 0;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
temp += map[i][j];
}
}
return temp;
}
}
반응형
'코테 > 백준' 카테고리의 다른 글
[백준 17142번] 연구소 3 lv > gold3 자바 (0) | 2023.07.27 |
---|---|
[백준 14500번] 자바 테트로미노 lv > gold4 (0) | 2023.07.26 |
[백준 14889번] 자바 스타트와 링크 lv > silver2 (0) | 2023.07.25 |
[백준 14888번] 자바 연산자 끼워넣기 lv > silver1 (0) | 2023.07.24 |
[backjoon] 25556번: 포스택 (0) | 2023.06.13 |