문제 풀이 날짜: 2023.10.10
포스트 작성일: 2023.10.16
* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.
문제 출처
구현, 시뮬레이션
키워드
백준 온라인 저지 17144번: 미세먼지 안녕! (골드4)
풀이 접근법
- 행렬의 모든 점을 중에서 미세먼지의 위치(Point)를 List로 취합하여 해당 부분을 중심으로 인접한 네 방향으로 확산시킨다.
- 단, List를 사용하면 메모리를 더 많이 차지하므로 행렬의 모든 점(R * C)을 탐색하는 것보다 효율적일 수도, 비효율적일 수도 있다.
- 미세먼지를 4방 확산시키면서, 미세먼지가 위치한 곳을 다시 List에 취합한다. 기존 미세먼지가 사라졌을 수도 있고, 기존에는 없었던 위치에 새 미세먼지가 생겼을 수도 있기 때문이다.
- 단, 미세먼지를 확산시킬 때에는 주의해야 할 점이 있다.
- 분산시킨 결과는 새 배열에 저장해주어야 한다.
- 그렇지 않으면 기존에 존재했던 미세먼지와 새로 밀려들어온 미세먼지가 합산되며 잘못된 결과가 나올 수 있다.
- 예를 들어, 미세먼지가 5만큼 있던 지점은 본래 사방으로 미세먼지를 1씩 확산시켜야 한다.
- 그런데 다른 지점으로부터 5만큼의 미세먼지가 흘러들어왔고, 현재 10의 미세먼지를 보유하게 되었다고 하자.
- 이 경우 사방으로 1이 아닌 2만큼의 미세먼지를 확산시키게 되는데, 이는 잘못된 값이다.
- 따라서 분산시킨 결과 배열(newMatrix)과 원본 배열(matrix)을 합산해서 확산 결과를 도출한다.
- 퍼트리기를 끝내면 공기청정기로 미세먼지를 청소(배열 돌리기 로직) 한다.
- 공기청정기를 기준으로 상단은 반시계 방향, 하단은 시계방향으로 흘러가므로 cleanUp(배열을 돌리는 메소드)을 위, 아래 두 번 호출해주었다.
- delta 배열은 시계방향, 반시계방향을 따로따로 선언해주었다.
- 미세먼지를 이동시킬 때에는 delta값을 따라 배열을 밀어주면 된다.
- 이때, 배열값을 밀고싶은 목적지(B)에 현재 위치(A)의 값을 대입하면서 밀면 B에 있는 배열값이 사라지게 되므로 주의한다.
- 예를 들어, (0,1) - (0,2) - (0,3) - ... 순으로 탐색할 때, (0,2)에 (0,1)의 값을 대입하면 그 다음에 (0,2)의 원래 값을 (0,3)에 대입할 수 없다.
- 따라서 B의 위치를 가리킨 상태에서 A 위치의 값을 끌어다 쓰는 형식으로 배열값을 대입힌다.
- 즉, (0,3) - (0,2) - (0,1) - ... 순으로 탐색하면서 (0,3) 위치에 (0,2)의 값을 대입하고 (0,2)로 포인터를 옮긴다. 그리고 (0,2)에 (0,1)의 값을 대입해준다. 이 과정을 공기청정기를 다시 만날 때까지 반복한다.
코드
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
private static int R;
private static int C;
private static int T;
private static int[][] matrix;
// 시계방향 delta (아래쪽)
private static int[] dr = { 1, 0, -1, 0 };
private static int[] dc = { 0, 1, 0, -1 };
// 반시계방향 delta (윗쪽)
private static int[] rdr = { -1, 0, 1, 0 };
private static int[] rdc = { 0, 1, 0, -1 };
private static List<Point> airCleaners = new ArrayList<>();
private static List<Point> dusts = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] temp = br.readLine().split(" ");
R = Integer.parseInt(temp[0]);
C = Integer.parseInt(temp[1]);
T = Integer.parseInt(temp[2]);
matrix = new int[R][C];
StringTokenizer st;
for (int i = 0; i < R; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < C; j++) {
matrix[i][j] = Integer.parseInt(st.nextToken());
if (matrix[i][j] == -1)
airCleaners.add(new Point(j, i));
if(matrix[i][j] > 0)
dusts.add(new Point(j, i));
}
}
int answer = solution(T, matrix);
System.out.println(answer);
}
private static int solution(int T, int[][] matrix) {
for (int t = 0; t < T; t++) {
int[][] newMatrix = new int[R][C];
// 1.미세먼지 확산
for (Point d : dusts) {
int i = d.y; int j = d.x;
if (matrix[i][j] != 0 && matrix[i][j] != -1) {
spread(i, j, matrix, newMatrix);
}
}
sumDust(matrix, newMatrix);
// 2.공기청정기로 미세먼지 날리기
cleanUp(airCleaners.get(0), airCleaners.get(1), rdr, rdc, matrix);
cleanUp(airCleaners.get(1), airCleaners.get(0), dr, dc, matrix);
// 3.미세먼지가 있는 곳 다시 수집
dusts.clear();
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if(matrix[i][j] > 0) dusts.add(new Point(j, i));
}
}
}
int count = 0; // 미세먼지량 세기
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (matrix[i][j] != 0 && matrix[i][j] != -1) {
count += matrix[i][j];
}
}
}
return count;
}
private static void sumDust(int[][] matrix, int[][] newMatrix) {
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
matrix[i][j] += newMatrix[i][j];
}
}
}
private static void spread(int r, int c, int[][] matrix, int[][] newMatrix) {
int count = 0;
int dust = (int) Math.floor(matrix[r][c] / 5);
int nr = 0;
int nc = 0;
for (int i = 0; i < dr.length; i++) {
nr = r + dr[i];
nc = c + dc[i];
if (!isValid(nr, nc) || matrix[nr][nc] == -1) {
continue;
}
newMatrix[nr][nc] += dust;
count += 1;
}
matrix[r][c] -= dust * count;
}
private static void cleanUp(Point point, Point anotherPoint, int[] dr, int[] dc, int[][] matrix) {
int currR = point.y;
int currC = point.x;
int dir = 0;
int nextR = currR;
int nextC = currC;
do {
nextR = currR + dr[dir];
nextC = currC + dc[dir];
if (!isValid(nextR, nextC)
|| nextR == anotherPoint.y) { // 벽에 부딪혔다면 or 반대편에 닿았다면 방향 전환
dir = (dir + 1) % 4;
continue;
}
if(matrix[currR][currC] != -1) {
matrix[currR][currC] = matrix[nextR][nextC];
}
if(matrix[currR][currC] == -1 && (currR != point.y || currC != point.x))
matrix[currR][currC] = 0;
currR = nextR; currC = nextC;
} while (!(nextR == point.y && nextC == point.x)); // 원점으로 돌아올 때까지 반복
}
private static boolean isValid(int nr, int nc) {
return (nr > -1 && nc > -1 && nr < R && nc < C);
}
}
리스트를 사용해서 그런지 다른 사람들의 코드에 비해 메모리와 시간이 많이 소모되었다. List뿐만 아니라 Set이나 Hash 등의 자료구조를 쓰면 특히 시간을 더 많이 소모하기 때문에, 언제나 최적의 효율을 보장하는 것은 아니다.