[백준] 17144번: 미세먼지 안녕! 문제 풀이

현톨·2023년 2월 14일
1

Algorithm

목록 보기
33/42

https://www.acmicpc.net/problem/17144

문제 접근 방식

문제를 읽고 미세먼지 확산과 공기청정기에 청정 기능을 각각 메서드로 구분지어야겠다는 생각이 들었다. 다만, 공기청정기로 먼지들을 각각 시계방향, 반시계 방향으로 동시에 회전시키기엔 헷갈릴 것 같아 윗부분, 아랫부분으로 메서드를 나누어 주었다.

  1. 먼지 확산 메서드를 통해 배열에 각 칸에 위치한 먼지를 상하좌우로 확산시킨다.
  2. 공기청정기 윗부분 (미세먼지 반시계 방향 회전)
  3. 공기청정기 아랫부분 (미세먼지 시계방향 회전)
  4. 1,2,3 과정 T번 반복

먼지 확산

배열의 칸마다 검사하면서 먼지가 존재하면 상하좌우 4방향을 확인하여 가능한 위치를 각각 newDust ArrayDeque에 넣어준다. 확산 가능할 때마다 cnt를 1씩 증가시켜준다.
이 때, 넣어주는 값은 (y값, x값, 먼지의 양 / 5)을 담은 배열이다.
배열 칸의 상하좌우를 수정시키지 않고, ArrayDeque에 넣어주는 이유는,
새로 확산된 먼지는 해당 초에서 확산하지 않기 때문이다.
따라서 현재 시각에 존재하는 먼지들이 확산시킬 먼지의 정보를 미리 담아놓고, 확산이 끝나면 그제서야 새로 확산된 먼지를 각 배열 칸에 추가해준다.

확산이 끝난 먼지는 기존 먼지량 - (기존 먼지랑 / 5 * 확산한 횟수 cnt)로 값을 변경해준다.

그리고 ArrayDeque의 요소들을 꺼내 해당 위치에 먼지들을 추가시켜준다.

static void spread() { // 먼지 확산 메서드
	ArrayDeque<int []> newDust = new ArrayDeque<>();
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			int difCnt = 0;
			int difDust = arr[i][j];
			for (int d = 0; d < 4; d++) {
            // 현재 칸의 4방향 검사하여 확산될 먼지 ArrayDeque에 추가
				int ny = i + dy[d];
				int nx = j + dx[d];
				if (0 <= ny && ny < R && 0 <= nx && nx < C && arr[ny][nx] != -1) {
					newDust.add(new int [] {ny, nx, difDust / 5});
					difCnt++;
				}
			}
            // 확산 후 기존 칸의 먼지량 수정
			arr[i][j] = difDust - (difDust / 5 * difCnt);
		}
	}
    // 모든 확산이 끝난 후, 확산된 먼지 각 칸에 추가
	while (!newDust.isEmpty()) {
		int [] yx = newDust.poll();
		arr[yx[0]][yx[1]] += yx[2];
	}
}

공기청정기

처음에 입력 받을 때, 공기청정기의 윗부분과 아랫부분의 위치를 각각 2차원 배열에 저장하였다.
ex) bot[0][0] = 공기청정기 윗부분의 y값, bot[1][1] = 공기청정기 아랫부분의 x값

공기청정기 메서드는 각각 현재 위치 y값, x값, 방향을 파라미터로 입력받는다.

윗부분 메서드
현재 이동하고자 하는 방향의 y값이 공기청정기 윗부분보다 작거나 같고, 배열의 범위 안에 있으면 재귀 호출을 통해 dps를 들어간다. 만약 이 때, 이동하려는 위치가 공기청정기가 있는 위치가 아니라면 이동하려는 위치의 먼지를 현재 위치로 끌어온다.
만약 이동할 수 없는 곳이라면 방향을 회전한다.
이동하려는 위치가 공기청정기가 있는 곳이라면 현재 위치는 0으로 바꿔준다.

static void cleanUp(int y, int x, int d) {
	int ny = y + dy[d];
	int nx = x + dx[d];
	if (ny == bot[0][0] && nx == bot[0][1]) {
		arr[y][x] = 0;
		return;
	}
	if (0 <= ny && ny <= bot[0][0] && 0 <= nx && nx < C) {
		if (!(y == bot[0][0] && x == bot[0][1]))
			arr[y][x] = arr[ny][nx];
		cleanUp(ny, nx, d);
	}
	else cleanUp(y, x, (d + 1) % 4);
}

아랫부분 메서드
윗부분 메서드와 달리 아랫부분 메서드는 방향 초기값을 아래로 설정해준다.
상우하좌 순으로 0123이라면 초기값을 2로 넣어준다.
또한 탐색 조건은 ny값이 아랫부분 메서드의 y값 이상이어야한다.
탐색할 수 없는 영역이라면 방향을 바꿔주는데,
이 때 상우좌하가 아닌 하좌상우 순으로 방향을 바꿔야한다.
그렇다면 2103이 되어야 하는데, 이는 (d+3)%4와 같다.

static void cleanDown(int y, int x, int d) {
	int ny = y + dy[d];
	int nx = x + dx[d];
	if (ny == bot[1][0] && nx == bot[1][1]) {
		arr[y][x] = 0;
		return;
	}
	if (bot[1][0] <= ny && ny < R && 0 <= nx && nx < C) {
		if (!(y == bot[1][0] && x == bot[1][1]))
			arr[y][x] = arr[ny][nx];
		cleanDown(ny, nx, d);
	}
	else cleanDown(y, x, (d + 3) % 4);
}

사실 공기청정기의 메서드는 재귀함수로 구현하지 않고 반복문으로 구현해도 충분할 것 같지만 재귀호출이 조금 더 직관성이 있는 것 같아 재귀함수로 구현하였다.

결과 출력

마지막으로 배열의 한칸씩 돌면서 모든 숫자를 더해준다.
그리고 공기청정기는 -1이기 때문에 마지막 결과에 2를 더해 출력한다.

전체코드

import java.io.*;
import java.util.*;

public class Main{
	static int [][] arr;
	static int R, C;
	static int [][] bot = new int[2][];
	static final int [] dy = {-1, 0, 1, 0}; // 상우하좌
	static final int [] dx = {0, 1, 0, -1};
	static void spread() {
		ArrayDeque<int []> newDust = new ArrayDeque<>();
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				int difCnt = 0;
				int difDust = arr[i][j];
				for (int d = 0; d < 4; d++) {
					int ny = i + dy[d];
					int nx = j + dx[d];
					if (0 <= ny && ny < R && 0 <= nx && nx < C && arr[ny][nx] != -1) {
						newDust.add(new int [] {ny, nx, difDust / 5});
						difCnt++;
					}
				}
				arr[i][j] = difDust - (difDust / 5 * difCnt);
			}
		}
		while (!newDust.isEmpty()) {
			int [] yx = newDust.poll();
			arr[yx[0]][yx[1]] += yx[2];
		}
	}
		
	static void cleanUp(int y, int x, int d) {
		int ny = y + dy[d];
		int nx = x + dx[d];
		if (ny == bot[0][0] && nx == bot[0][1]) {
			arr[y][x] = 0;
			return;
		}
		if (0 <= ny && ny <= bot[0][0] && 0 <= nx && nx < C) {
			if (!(y == bot[0][0] && x == bot[0][1]))
				arr[y][x] = arr[ny][nx];
			cleanUp(ny, nx, d);
		}
		else cleanUp(y, x, (d + 1) % 4);
	}
	
	static void cleanDown(int y, int x, int d) {
		int ny = y + dy[d];
		int nx = x + dx[d];
		if (ny == bot[1][0] && nx == bot[1][1]) {
			arr[y][x] = 0;
			return;
		}
		if (bot[1][0] <= ny && ny < R && 0 <= nx && nx < C) {
			if (!(y == bot[1][0] && x == bot[1][1]))
				arr[y][x] = arr[ny][nx];
			cleanDown(ny, nx, d);
		}
		else cleanDown(y, x, (d + 3) % 4);
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		int T = Integer.parseInt(st.nextToken());
		int pos = 0;
		arr = new int [R][C];
		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < C; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				if (arr[i][j] == -1) bot[pos++] = new int [] {i, j};
			}
		}
		for (int i = 0; i < T; i++) {
			spread();
			cleanUp(bot[0][0], bot[0][1], 0);
			cleanDown(bot[1][0], bot[1][1], 2);
		}
		int ans = 0;
		for (int i = 0; i < R; i++)
			for (int j = 0; j < C; j++) 
				ans += arr[i][j];
		System.out.println(ans + 2);
	}
}
profile
기록하는 습관 들이기

0개의 댓글