문제 링크입니다: https://www.acmicpc.net/problem/17144
17144번: 미세먼지 안녕!
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼
www.acmicpc.net
미세먼지의 확산이 동시다발적으로 일어나기 때문에 배열을 복사해야하는 점이 귀찮았지만 재밌는 문제였습니다.
알고리즘은 아래와 같습니다.
1. 매 초마다 미세먼지의 확산을 진행하는데 BFS 알고리즘을 적용하듯이 4 방향을 모두 탐색하여 범위 안에 있는 칸이면 각 칸마다 (해당 칸의 미세먼지 크기 / 5)를 더해주고 해당 칸에서는 그만큼 빼주면 됩니다.
1.1 여기서 주의할 점은 배열을 계속 업데이트하면 동시다발적으로 이루어지는 것이 아니기 때문에 복사한 배열에서 미세먼지 여부를 파악하고 미세먼지 양 업데이트는 실제 배열에다가 해주면 됩니다.
2. 공기청정기도 마찬가지로 현재 배열을 복사한 상태에서 전처리를 해주면 편합니다.
2.1 반시계 방향, 시계 방향으로 공기가 흐르기 때문에 미리 ccw, cw 배열을 잡아 움직이는 방향 인덱스를 저장해주는 것이 편합니다.
2.2 반복문의 탈출 조건을 잘 잡는다면 쉽게 공기의 흐름대로 미세먼지를 이동시킬 수 있습니다.
3. 현재 배열에 있는 미세먼지의 크기들을 모두 합친 뒤 출력합니다.
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 12116번 Uzastopni (0) | 2019.05.15 |
|---|---|
| 백준 12115번 Baza (0) | 2019.05.15 |
| 백준 17143번 낚시왕 (4) | 2019.05.09 |
| 백준 17142번 연구소 3 (3) | 2019.05.08 |
| 백준 17140번 이차원 배열과 연산 (2) | 2019.05.08 |