[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();
}
}
CLOSING
삼성 기출은 항상 풀면서 '실수 없이 요구하는 사항을 구현해!' 라는 느낌을 많이 받습니다.
문제의 요구사항에 맞도록 코드를 작성하면 되기 때문에 별도로 특이한 알고리즘이나 자료구조는 사용하지 않았습니다.
한번에 내가 의도하는 비즈니스 로직을 실수 없이 작성할 수 있는 연습이 필요합니다.