(JAVA) 백준 17144번 : 미세먼지 안녕!

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

17144번: 미세먼지 안녕!

 

 

삼성 SW 기출 문제집 문제 중 하나로

 

시뮬레이션 문제.

 

 

 

문제에 주어진 조건에 맞게 알고리즘을 구현하면 된다.

 

 

 

주의 깊게 볼 부분 중 하나는

 

 

바로 이부분이다.

 

" 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다. "

 

 

 

그렇기 때문에

 

2차원 배열 map을 순차적으로 탐색하지만

 

앞선 미세먼지가 확산됨에 따라 

 

다음 미세먼지의 양이 변하고, 그 변한 양을 가지고 확산하는 것이 아닌

 

전부 확산 전의 미세먼지 양을 가지고 계산해야 한다.

 

 

문제의 예제에서도 보면

 

 

30 -> 12, 주위 6

7 -> 5, 주위 1

10 -> 4, 주위 2

20 -> 12, 주위 4

 

 

로 일괄 확산한 후, 주위로 퍼져 나간 미세먼지 양을 한 번에 더했다.

 

 

 

 

 

다음으로, 형광펜으로 칠한 부분을 보면

 

" 확산되는 양은 A(r,c) / 5 이고, 소수점은 버린다. "

 

라고 하는데

 

 

말 그대로 소수점을 버리기 때문에

 

미세먼지가 5보다 작은 것들은 굳이 확산 계산을 하지 않고 넘어가도 된다.

 

 

5를 나누면 0이 나오니까.

 

 

 

 

 

이 외에는 특별히 유의할 점은 없고,

 

공기 청정기가 있는 곳에는 확산이 없기 때문에 -1을 유지하고 있으며,

 

모든 미세먼지 양을 더할 때 -1을 더하지 않도록 예외 처리가 필요하다.

 

 

 

또, 바람에 의해 미세먼지가 한 칸 밀려나가는 것을 구현하기 위해

 

시계 / 반시계 방향에 따른 distance 값을 통해 x, y 좌표 값을 변화시키며 

 

내부 원소 값을 이동시켰다.

*** 그래서 Map을 벗어나는 순간 distance의 값(방향)을 변화시킨다.

 

 

 

 

매커니즘

---

1. 2차원 int 배열 2개를 생성한다.

  -> 하나는 현재 미세먼지의 양을 담는 Map

  -> 다른 하나는 확산 및 바람에 의한 이동 시 증감하는 미세먼지의 양을 담는 Map

 

 

2. 입력값 받기

  -> 이 때, 공기청정기(-1) 의 Y좌표 값을 별도 Array(저는 ArrayList를 사용) 에 저장한다.

*** Y좌표 값만 저장하는 이유는 문제에서 공기청정기는 무조건 x = 0 의 위치에 있다고 가정했기 때문이다.

 

 

3. 공기청정기 Array를 Sort해서 윗부분과 아랫 부분을 구분짓는다.

*** 오름차순 정렬하면 무조건 index = 0 은 윗부분, index = 1은 아랫부분이 된다.

 

 

4. (while) T초가 될 때 까지 반복 수행

 

4 - 1. 미세먼지 확산 작업 진행

 

4 - 2. 확산으로 인해 증감된 미세먼지 계산하는 작업 진행

 

4 - 3. 공기청정기로 바람불기

*** 저는 moveX, moveY 라는 1차원 int 배열을 선언하고 진행했습니다. 

**** 소스코드 참고 바람

 

 

*** 위 그림은 바람이 불면서 미세먼지를 어떻게 이동시키는지 갤럭시 노트로 그려봤습니다.

 

1) 현재 위치의 미세먼지 양을 다음 위치의 미세먼지 증감 Map(movedMap) 에 저장한다.

 

2) 현재 위치의 미세먼지 증감 Map(movedMap) 에서 값을 가져와 미세먼지 Map(map) 에 대입한다.

 

3) 현재 위치의 미세먼지 증감 Map(movedMap) 을 0으로 초기화한다.

 

 

 

 

 

더 자세한 사항은 소스코드(+ 주석)를 보시면 될 것 같습니다.

 

감사합니다!

 

소스코드

---

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.ArrayList;
	import java.util.Collections;
	import java.util.StringTokenizer;
	// 미세먼지 안녕! 문제
	// 시뮬레이션
	public class p17144 {
	static int r, c, t;
	static ArrayList<Integer> fresher; // x좌표는 무조건 1이므로, y좌표 값만 담아서 sort 진행하면 [0]이 up, [1]이 down.
	static int[][] map, movedMap; // 기존 미세먼지 담은 맵, 미세먼지 분산 후 증가량 담은 맵
	// 이동 방향은 왼 - 아래 - 오른 - 위 순서
	static int[] moveX = { 1, 0, -1, 0 };
	static int[] moveY = { 0, 1, 0, -1 };
	public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	r = Integer.valueOf(st.nextToken());
	c = Integer.valueOf(st.nextToken());
	t = Integer.valueOf(st.nextToken());
	map = new int[r][c];
	movedMap = new int[r][c];
	fresher = new ArrayList<Integer>();
	for(int i = 0; i < r; i++) {
	st = new StringTokenizer(br.readLine());
	for(int j = 0; j < c; j++) {
	int dust = Integer.valueOf(st.nextToken());
	map[i][j] = dust;
	// 공기 청정기
	if(dust == -1) {
	fresher.add(i);
	}
	}
	}
	// 공기 청정기 UP, DOWN 확정
	Collections.sort(fresher);
	// 1초 동안 일 진행
	int nowTime = 0;
	while(nowTime < t) {
	spread();
	setDustAfterSpread();
	moveWind(true); // UP
	moveWind(false); // DOWN
	nowTime++;
	}
	// 미세먼지 총 양 계산
	int allDust = 0;
	for(int y = 0; y < r; y++) {
	for(int x = 0; x < c; x++) {
	if(map[y][x] > 0) {
	allDust += map[y][x];
	}
	}
	}
	System.out.println(allDust);
	}
	// 미세먼지 확산
	static void spread() {
	for(int y = 0; y < r; y++) {
	for(int x = 0; x < c; x++) {
	if(map[y][x] >= 5) { // 5 미만의 수는 5로 나누면 0이라서 의미 없다.
	int movedDust = map[y][x] / 5;
	int count = 0;
	for(int i = 0; i < moveX.length; i++) {
	int nextX = x + moveX[i];
	int nextY = y + moveY[i];
	// 벽에 닿으면
	if(nextY < 0 || nextY >= r || nextX < 0 || nextX >= c) {
	continue;
	}
	// 공기 청정기
	if(map[nextY][nextX] == -1) {
	continue;
	}
	movedMap[nextY][nextX] += movedDust;
	count++;
	}
	map[y][x] = map[y][x] - (movedDust * count); // 계산 제대로 되는지 확인
	}
	}
	}
	}
	// 확산된 미세먼지 맵에 값 추가하기
	static void setDustAfterSpread() {
	for(int y = 0; y < r; y++) {
	for(int x = 0; x < c; x++) {
	if(movedMap[y][x] > 0) {
	map[y][x] += movedMap[y][x];
	movedMap[y][x] = 0;
	}
	}
	}
	}
	// 공기 청정기 바람 이동
	// @param : isUp : True - UP 청정기, False - DOWN 청정기
	static void moveWind(boolean isUp) {
	int startX = 1;
	int startY = isUp ? fresher.get(0) : fresher.get(1);
	int endY = startY;
	int direction = 0;
	while(startX != 0 || startY != endY) {
	int nextX = startX + moveX[direction];
	int nextY = startY + moveY[direction];
	// 벽에 닿으면
	if(nextY < 0 || nextY >= r || nextX < 0 || nextX >= c) {
	if(isUp) {
	direction = direction == 0 ? 3 : direction - 1;
	}
	else {
	direction++;
	}
	continue;
	}
	// 바람 이동
	movedMap[nextY][nextX] = map[startY][startX];
	map[startY][startX] = movedMap[startY][startX];
	movedMap[startY][startX] = 0;
	startX = nextX;
	startY = nextY;
	}
	movedMap[startY][startX] = 0;
	}
	}

view raw p17144.java hosted with ❤ by GitHub