(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으로 초기화한다.

 

 

 

 

 

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

 

감사합니다!

 

소스코드

---