알고리즘
[백준] 미세먼지 안녕! - Java
BGK97
2025. 1. 17. 18:50
문제
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.
공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.
1초 동안 아래 적힌 일이 순서대로 일어난다.
- 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
- (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
- 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
- 확산되는 양은 Ar,c/5이고 소수점은 버린다. 즉, ⌊Ar,c/5⌋이다.
- (r, c)에 남은 미세먼지의 양은 Ar,c - ⌊Ar,c/5⌋×(확산된 방향의 개수) 이다.
- 공기청정기가 작동한다.
- 공기청정기에서는 바람이 나온다.
- 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
- 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
- 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.
다음은 확산의 예시이다.
공기청정기의 바람은 다음과 같은 방향으로 순환한다.
방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.
입력
첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.
둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.
출력
첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.
예제 입력 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문제 풀이
- 구현이라 시간을 많이 썼다.
- 미세먼지 확산은 공식이 있었기에 쉽게 dfs를 활용해 적용할 수 있었으나, 공기청정기 순환에서 값을 옮기는 과정에서 조금 오래걸렸던 것 같다.
- 확산시에는 복사 배열을 생성하여 배열 전체를 순환하여 복사 배열에 그 값을 저장해서 옮겨주었다.
// 복사 배열 생성 후 계산하고 복사배열에 옮기기
public static void spreadDust() {
int[][] newRoom = new int[R][C];
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
// 0인경우는 확산 안하므로
int spreadValue = room[i][j] / 5;
int spreadCount = 0;
if (room[i][j] > 0) {
for (int d = 0; d < 4; d++) {
// 4방 탐색 수행
int nr = i + dr[d];
int nc = j + dc[d];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && room[nr][nc] != -1) {
newRoom[nr][nc] += spreadValue;
spreadCount++;
}
}
// 가운데는 확산 후 남은 먼지를 저장한다.
newRoom[i][j] += room[i][j] - (spreadValue * spreadCount);
}
}
}
// 과정이 끝나면 배열에 다시 값 옮김
room = newRoom;
}- 이 과정으로 본 배열에는 영향을 끼치지 않고 정상적으로 계산을 끝낸 후, 다시 옮길 수 있었다.
문제의 공기청정기 순환
- 초기에는 순차적으로 공기청정기 옆부터 시작하여 순환하려고 하니, 마지막 값이 사라져 애를 먹었다. 저장을 하자니 다음 반복분에서 쓸 곳이 애매하고...
- 그래서 생각을하다가 값이 밀리는 것을 확인하고, 끝부터 밀어버리면 저장할 필요도 없겠다! 라는 생각이 들었고, 그대로 코드에 옮기기 시작했다.
// 반시계 회전
for (int i = top - 1; i > 0; i--) {
room[i][0] = room[i - 1][0];
}
for (int i = 0; i < C - 1; i++) {
room[0][i] = room[0][i + 1];
}
for (int i = 0; i < top; i++) {
room[i][C - 1] = room[i + 1][C - 1];
}
for (int i = C - 1; i > 1; i--) {
room[top][i] = room[top][i - 1];
}
// 시계 회전
for (int i = bottom + 1; i < R - 1; i++) {
room[i][0] = room[i + 1][0];
}
for (int i = 0; i < C - 1; i++) {
room[R - 1][i] = room[R - 1][i + 1];
}
for (int i = R - 1; i > bottom; i--) {
room[i][C - 1] = room[i - 1][C - 1];
}
for (int i = C - 1; i > 1; i--) {
room[bottom][i] = room[bottom][i - 1];
}- 이후에 공기 청정기에서 옆으로 옮겨진 값은 0으로 초기화를 해주면서 테스트케이스를 통과했다.
- 근데 틀렸다. 분명 로직엔 이상이 없다고 생각했고, 왜 틀린건지 고민하다가...
room[top][0] = -1;
room[bottom][0] = -1;- 이 두줄을 깜빡했다. 순환 중에 공기청정기에도 값이 들어가는 예외상황을 생각을 못했다...
풀이 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int R, C, T;
static int[][] room;
static int[] airPurifier = new int[2];
static int[] dr = { -1, 1, 0, 0 };
static int[] dc = { 0, 0, -1, 1 };
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());
T = Integer.parseInt(st.nextToken());
room = new int[R][C];
int airIdx = 0;
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) {
airPurifier[airIdx++] = i;
}
}
}
// 주기동안 순환 반복하기
for (int i = 0; i < T; i++) {
// 1. 미세먼지 확산
spreadDust();
// 2. 공기청정기 작동
airPurifierOperation();
}
int sum = 0;
// 전체 미세먼지 합 구하기
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
// 공기청정기 제외
if (room[i][j] > 0) {
sum += room[i][j];
}
}
}
System.out.println(sum);
}
// 복사 배열 생성 후 계산하고 복사배열에 옮기기
public static void spreadDust() {
int[][] newRoom = new int[R][C];
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
// 0인경우는 확산 안하므로
int spreadValue = room[i][j] / 5;
int spreadCount = 0;
if (room[i][j] > 0) {
for (int d = 0; d < 4; d++) {
// 4방 탐색 수행
int nr = i + dr[d];
int nc = j + dc[d];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && room[nr][nc] != -1) {
newRoom[nr][nc] += spreadValue;
spreadCount++;
}
}
// 가운데는 확산 후 남은 먼지를 저장한다.
newRoom[i][j] += room[i][j] - (spreadValue * spreadCount);
}
}
}
// 과정이 끝나면 배열에 다시 값 옮김
room = newRoom;
}
public static void airPurifierOperation() {
int top = airPurifier[0];
int bottom = airPurifier[1];
// 반시계 회전
for (int i = top - 1; i > 0; i--) {
room[i][0] = room[i - 1][0];
}
for (int i = 0; i < C - 1; i++) {
room[0][i] = room[0][i + 1];
}
for (int i = 0; i < top; i++) {
room[i][C - 1] = room[i + 1][C - 1];
}
for (int i = C - 1; i > 1; i--) {
room[top][i] = room[top][i - 1];
}
// 시계 회전
for (int i = bottom + 1; i < R - 1; i++) {
room[i][0] = room[i + 1][0];
}
for (int i = 0; i < C - 1; i++) {
room[R - 1][i] = room[R - 1][i + 1];
}
for (int i = R - 1; i > bottom; i--) {
room[i][C - 1] = room[i - 1][C - 1];
}
for (int i = C - 1; i > 1; i--) {
room[bottom][i] = room[bottom][i - 1];
}
room[top][1] = 0;
room[bottom][1] = 0;
room[top][0] = -1;
room[bottom][0] = -1;
}
}결과
회고
- 깡구현 극혐