[SW 역량테스트 기출풀이] 백준 - 17144 미세먼지 안녕!

 문제 

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

17144번: 미세먼지 안녕!

 해설 

단순구현 시뮬레이션 문제입니다. 문제의 조건을 간단히 정리하자면 아래와 같습니다.

 

• 공기청정기는 첫번째 열에서 2행을 차지하며 가장 윗 행과 아랫 행에서 두 칸 이상 떨어져있다.
• 공기청정기의 윗부분은 반시계 방향으로 아랫부분은 시계방향으로 순환하며 먼지를 한 칸씩 민다.
• 미세먼지는 매 초마다 위, 아래, 왼쪽, 오른쪽으로 확산된다.
• 특정 좌표에서의 미세먼지의 크기가 A라고 했을 때 확산되는 미세먼지는 A / 5이고 해당 좌표에서는 확산된 미세먼지의 크기 만큼 미세먼지의 크기가 줄어든다.
• 공기청정기에 들어간 미세먼지는 정화되서 사라진다.

 

여기서 처리해야할 동작은 미세먼지와 공기청정기 동작으로 나눌 수 있는데 각각 다음과 같은 사항을 고려해서 구현해야합니다.

 

미세먼지 

• 미세먼지는 공기청정기가 있는 곳에는 확산되지 못한다.
• 미세먼지는 기존에 미세먼지가 있는 곳으로 확산되어 지지만 미세먼지는 매 초에 동시에 확산되어지므로 이를 기준으로 미세먼지의 양을 갱신할 때 주의해야 한다.

 

공기청정기

• 공기 청정기에서 나오는 바람의 경로의 미세먼지들을 한 칸씩 밀어야하며, 공기청정기에 들어간 먼지는 사라진다.
• 바람은 순환방향으로 이동한다.
• 공기청정기는 상/하로 나누어져 있다.

 

코드를 보며 설명을 이어가도록 하겠습니다.

 

 구현 

import java.util.*;

public class Main {
	static StringBuilder sb = new StringBuilder();
	// 행 r, 열 c, 시간 t
	static int r, c, t;
	static int[][] map;
	// 공기청정기의 행 좌표를 저장할 배열, 공기청정기의 열좌표는 고정이다.
	static int[] cr;
	
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	static void dust() {	
		// 각 미세먼지의 확산을 기록할 배열 
		int[][] spread = new int[r][c];
		for(int i = 0; i<r; i++) {
			for(int j = 0; j<c; j++) {
				// 미세먼지를 발견하면
				if(map[i][j] > 0) {
					// 확산될 양을 기록한다.
					int div = map[i][j] / 5;
					for(int dir = 0; dir<4; dir++) {
						int nx = i + dx[dir];
						int ny = j + dy[dir];
						// 확산될 좌표가 유효한 범위 내에 존재하는지, 확산될 곳이 공기청정기인지 검사한다.
						if(nx < 0 || nx >= r || ny < 0 || ny >= c || map[nx][ny] == -1) continue;
						// 두가지 경우가 아니라면 확산을 기록할 배열에 확산된 좌표에 확산 양만큼
						// 더하여 기록한다.
						spread[nx][ny] += div;
						// 기존의 미세먼지는 확산된 만큼 크기가 감소한다.
						map[i][j] -= div;
					}
				}
			}
		}
		// 확산된 미세먼지만큼 각 좌표를 갱신한다.
		for(int i = 0; i<r; i++) {
			for(int j = 0; j<c; j++) {
				map[i][j] += spread[i][j];
			}
		}
	}
	
	static void cleaner() {
		// 탐색방향은 공기청정기 순환방향의 역방향
		// 공기청정기의 윗부분은 반시계 방향이므로 시계방향으로 탐색
		int udir = 0;
		// 공기청정기 윗부분의 좌표
		int ur = cr[0];
		int uc = 0;
		while(true) {
			// 탐색할 좌표
			int nx = ur + dx[udir];
			int ny = uc + dy[udir];
			// 탐색할 좌표가 다시 공기청정기 이면 한바퀴 다 돈 것이므로 종료
			if(nx == cr[0] && ny == 0)
				break;
			// 만약 탐색할 좌표가 범위를 벗어났으면 방향을 바꾸어준다. 
			// 시계방향이므로 방향은 위 -> 오른쪽 -> 아래 -> 왼쪽 순서이다.
			if(nx < 0 || nx >= cr[1] || ny < 0 || ny >= c) {
				udir = (udir + 1) % 4;
			}else {
				// 해당 좌표에 미세먼지가 존재하지 않으면 넘어간다.
				if(map[nx][ny] != 0) {
					// 미세 먼지가 들어갈 곳인 이전좌표 (ur, uc)가 공기청정기이면
					if(ur == cr[0] && uc == 0) {
						// 미세먼지를 제거한다.
						map[nx][ny] = 0;
					}else {
						// 해당 미세먼지는 이전 좌표로 이동하고 
						// 해당 좌표의 미세먼지는 이동했으므로 0으로 초기화한다.
						map[ur][uc] = map[nx][ny];
						map[nx][ny] = 0;
					}
				}
				// 이전 좌표를 현재 좌표로 갱신합니다.
				ur = nx;
				uc = ny;
			}
		}
		
		// 탐색방향은 공기청정기 순환방향의 역방향
		// 공기청정기의 아랫부분은 시계 방향이므로 반시계방향으로 탐색
		int ddir = 2;
		// 공기청정기의 아랫부분 좌표
		int dr = cr[1];
		int dc = 0;
		while(true) {
			// 탐색할 좌표
			int nx = dr + dx[ddir];
			int ny = dc + dy[ddir];
			// 탐색할 좌표가 다시 공기청정기 이면 한바퀴 다 돈 것이므로 종료
			if(nx == cr[1] && ny == 0)
				break;
			// 만약 탐색할 좌표가 범위를 벗어났으면 방향을 바꾸어준다. 
			// 반시계방향이므로 방향은 아래 -> 오른쪽 -> 위 -> 왼쪽 순서이다.
			if(nx < cr[1] || nx >= r || ny < 0 || ny >= c) {
				ddir = (ddir + 3) % 4;
			}else {
				if(map[nx][ny] != 0) {
					if(dr == cr[1] && dc == 0) {
						map[nx][ny] = 0;
					}else {
						map[dr][dc] = map[nx][ny];
						map[nx][ny] = 0;
					}
				}
				dr = nx;
				dc = ny;
			}
		}
	}

	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());
		t = Integer.parseInt(st.nextToken());
		map = new int[r][c];
		cr = new int[2];
		int idx = 0;
		
		for(int i = 0; i<r; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j<c; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == -1) {
					cr[idx++] = i;
				}
			}
		}
		// 시간 t 만큼 미세먼지의 확산과 공기청정기의 동작을 반복한다.
		while(t > 0) {
			dust();
			cleaner();
			t--;
		}
		int total = 0;
		// 남아있는 미세먼지를 계산한다.
		for(int i = 0; i<r; i++) {
			for(int j = 0; j<c; j++) {
				if(map[i][j] == 0 || map[i][j] == -1) continue;
				total += map[i][j];
			}
		}
		System.out.println(total);
	}
}

코드를 구현하면서 공기청정기의 순환을 처리하는 부분이 조금 까다롭습니다.

 

공기 청정기는 각 시계방향과 반시계 방향으로 돌면서 미세먼지를 한 칸씩 밀지만, 이와 같이 할 경우 다음 칸에 미세먼지가 존재하면 이를 처리하는 과정이 복잡하므로 역방향으로 탐색하여 미세먼지를 한 칸씩 끌어당겨 주도록 합시다.

 

또한 공기청정기가 순환하는 유효범위는 상/하를 구분하여 각각의 행 범위를 잘 조절해주도록 하는 것이 포인트 입니다.