[BOJ] 미세먼지 안녕!
1. 문제 Link
2. 문제 설명
문제 Link를 참고하세요.
3. 입출력 예
3.1. 입력
- 첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.
- 둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다.
- 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다.
- -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.
3.2. 출력
- 첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.
문제 Link를 참고하세요.
4. 코드 해설
4.1. main 코드
- 전달 받은 시간(T) 동안 각 시간마다 확산(diffusion)과 환기(refresh)를 수행합니다.
- 모든 시간이 지난 뒤 맵에 존재하는 먼지 총 합을 계산하여 출력합니다.
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int R = sc.nextInt();
int C = sc.nextInt();
int T = sc.nextInt();
// map 정보 생성
int[][] map = new int[R][C];
for (int row = 0; row < R; row++) {
for (int col = 0; col < C; col++) {
map[row][col] = sc.nextInt();
}
}
for (int time = 0; time < T; time++) {
diffusion(map);
refresh(map);
}
System.out.println(sumDust(map));
sc.close();
}
4.2. 확산(diffusion)
- map 변수에 값을 엎어치면 배열 뒷 부분에 위치한 값들의 계산 결과가 달라지게 됩니다.
- diffuseMap 이라는 임시 배열을 만들고 여기에 계산된 값을 저장합니다.
- 계산된 값이 diffuseMap에 모두 저장되었으면 diffuseMap 배열의 값들을 map 배열에 다시 복사합니다.
- 청소기 위치는 SKIP 합니다.
public static void diffusion(int[][] map) {
int R = map.length;
int C = map[0].length;
int[][] diffusedMap = new int[R][C];
for (int row = 0; row < R; row++) {
for (int col = 0; col < C; col++) {
if (map[row][col] == -1) {
diffusedMap[row][col] = -1;
continue;
}
int cnt = 0;
int value = map[row][col] / 5;
if (row - 1 >= 0 && map[row - 1][col] != -1) {
cnt++;
diffusedMap[row - 1][col] += value;
}
if (row + 1 < R && map[row + 1][col] != -1) {
cnt++;
diffusedMap[row + 1][col] += value;
}
if (col - 1 >= 0 && map[row][col - 1] != -1) {
cnt++;
diffusedMap[row][col - 1] += value;
}
if (col + 1 < C && map[row][col + 1] != -1) {
cnt++;
diffusedMap[row][col + 1] += value;
}
diffusedMap[row][col] = diffusedMap[row][col] + map[row][col] - cnt * value;
}
}
for (int row = 0; row < R; row++) {
System.arraycopy(diffusedMap[row], 0, map[row], 0, C);
}
}
4.3. 환기(refresh)
- 반시계 방향 회전과 시계 방향 회전 환기를 수행합니다.
- 각 방향의 마지막 위치부터 값을 이동시킵니다.
- 각 코너 부분에서 값이 정상적으로 이동되지 않을 수 있으니 이 부분을 주의해야합니다.
- (0, 0), (0, C-1), (r, C-1), (R-1, 0), (R-1, C-1), (r, C-1)
public static void refresh(int[][] map) {
int r = 0;
int R = map.length;
int C = map[0].length;
for (int row = 0; row < R; row++) {
if (map[row][0] == -1) {
r = row;
break;
}
}
// 반시계 회전
int row = r - 1;
int col = 0;
while (!(r == row && col == 0)) {
if (col == 0 && row != 0) {
map[row + 1][col] = (map[row + 1][col] == -1) ? -1 : map[row][col];
row--;
} else if (row == 0 && col == 0) {
map[row + 1][col] = map[row][col];
col++;
} else if (row == 0 && col != C - 1) {
map[row][col - 1] = map[row][col];
col++;
} else if (row == 0 && col == C - 1) {
map[row][col - 1] = map[row][col];
row++;
} else if (col == C - 1 && row != r) {
map[row - 1][col] = map[row][col];
row++;
} else if (col == C - 1 && row == r) {
map[row - 1][col] = map[row][col];
col--;
} else {
map[row][col + 1] = map[row][col];
col--;
}
}
map[row][col + 1] = 0;
r++;
row = r + 1;
col = 0;
// 시계 회전
while (!(r == row && col == 0)) {
if (col == 0 && row != R - 1) {
map[row - 1][col] = (map[row - 1][col] == -1) ? -1 : map[row][col];
row++;
} else if (col == 0 && row == R - 1) {
map[row - 1][col] = map[row][col];
col++;
} else if (row == R - 1 && col != C - 1) {
map[row][col - 1] = map[row][col];
col++;
} else if (row == R - 1 && col == C - 1) {
map[row][col - 1] = map[row][col];
row--;
} else if (col == C - 1 && row != r) {
map[row + 1][col] = map[row][col];
row--;
} else if (col == C - 1 && row == r) {
map[row + 1][col] = map[row][col];
col--;
} else {
map[row][col + 1] = map[row][col];
col--;
}
}
map[row][col + 1] = 0;
}
5. 제출 코드
import java.util.Scanner;
public class Main {
public static void diffusion(int[][] map) {
int R = map.length;
int C = map[0].length;
int[][] diffusedMap = new int[R][C];
for (int row = 0; row < R; row++) {
for (int col = 0; col < C; col++) {
if (map[row][col] == -1) {
diffusedMap[row][col] = -1;
continue;
}
int cnt = 0;
int value = map[row][col] / 5;
if (row - 1 >= 0 && map[row - 1][col] != -1) {
cnt++;
diffusedMap[row - 1][col] += value;
}
if (row + 1 < R && map[row + 1][col] != -1) {
cnt++;
diffusedMap[row + 1][col] += value;
}
if (col - 1 >= 0 && map[row][col - 1] != -1) {
cnt++;
diffusedMap[row][col - 1] += value;
}
if (col + 1 < C && map[row][col + 1] != -1) {
cnt++;
diffusedMap[row][col + 1] += value;
}
diffusedMap[row][col] = diffusedMap[row][col] + map[row][col] - cnt * value;
}
}
for (int row = 0; row < R; row++) {
System.arraycopy(diffusedMap[row], 0, map[row], 0, C);
}
}
public static void refresh(int[][] map) {
int r = 0;
int R = map.length;
int C = map[0].length;
for (int row = 0; row < R; row++) {
if (map[row][0] == -1) {
r = row;
break;
}
}
// 반시계 회전
int row = r - 1;
int col = 0;
while (!(r == row && col == 0)) {
if (col == 0 && row != 0) {
map[row + 1][col] = (map[row + 1][col] == -1) ? -1 : map[row][col];
row--;
} else if (row == 0 && col == 0) {
map[row + 1][col] = map[row][col];
col++;
} else if (row == 0 && col != C - 1) {
map[row][col - 1] = map[row][col];
col++;
} else if (row == 0 && col == C - 1) {
map[row][col - 1] = map[row][col];
row++;
} else if (col == C - 1 && row != r) {
map[row - 1][col] = map[row][col];
row++;
} else if (col == C - 1 && row == r) {
map[row - 1][col] = map[row][col];
col--;
} else {
map[row][col + 1] = map[row][col];
col--;
}
}
map[row][col + 1] = 0;
r++;
row = r + 1;
col = 0;
// 시계 회전
while (!(r == row && col == 0)) {
if (col == 0 && row != R - 1) {
map[row - 1][col] = (map[row - 1][col] == -1) ? -1 : map[row][col];
row++;
} else if (col == 0 && row == R - 1) {
map[row - 1][col] = map[row][col];
col++;
} else if (row == R - 1 && col != C - 1) {
map[row][col - 1] = map[row][col];
col++;
} else if (row == R - 1 && col == C - 1) {
map[row][col - 1] = map[row][col];
row--;
} else if (col == C - 1 && row != r) {
map[row + 1][col] = map[row][col];
row--;
} else if (col == C - 1 && row == r) {
map[row + 1][col] = map[row][col];
col--;
} else {
map[row][col + 1] = map[row][col];
col--;
}
}
map[row][col + 1] = 0;
}
public static int sumDust(int[][] map) {
int result = 0;
int R = map.length;
int C = map[0].length;
for (int row = 0; row < R; row++) {
for (int col = 0; col < C; col++) {
if (map[row][col] != -1) {
result += map[row][col];
}
}
}
return result;
}
public static void print(int[][] map) {
int R = map.length;
int C = map[0].length;
for (int row = 0; row < R; row++) {
for (int col = 0; col < C; col++) {
System.out.print(map[row][col] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int R = sc.nextInt();
int C = sc.nextInt();
int T = sc.nextInt();
// map 정보 생성
int[][] map = new int[R][C];
for (int row = 0; row < R; row++) {
for (int col = 0; col < C; col++) {
map[row][col] = sc.nextInt();
}
}
for (int time = 0; time < T; time++) {
diffusion(map);
refresh(map);
}
System.out.println(sumDust(map));
sc.close();
}
}
댓글남기기