[백준 / Java] 17144번: 미세먼지 안녕! (골드4)

문제 풀이 날짜: 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 등의 자료구조를 쓰면 특히 시간을 더 많이 소모하기 때문에, 언제나 최적의 효율을 보장하는 것은 아니다.