[C++] 백준 17144번 미세먼지 안녕!

17144번: 미세먼지 안녕!

구현 / 시뮬레이션 문제.

처음에 상, 하, 좌, 우를 움직이길래 BFS문제인 줄 알았는데 아니였다.

(BFS와 비슷하게 구현하긴 했다.)

삼성 SW기출문제에 나와있는 문제다. 골드4 문제치고 반례같은 것도 없었다. 정답률도 높은 편이였다.

 

문제풀이

문제를 다음과 같은 순서대로 구현만 해주면 된다.

 

1. 미세먼지 확산. 이 때 상, 하, 좌, 우 방향으로 확산되는데 확산되는 미세먼지의 양은 A/5이다.

그런데 확산되는 방향 중 공기청정기가 있거나, 공간이 없는 경우에는 확산이 되지 않는다.

확산되고 남은 미세먼지의 양은 ( 원래 미세먼지양 - ( A/5 * 확산된 방향의 개수) )가 된다.

여기서 우리가 알 수 있는 것은, 5보다 작은 미세먼지는 확산되지 않는다는 것이다.

따라서 5 이상의 미세먼지들만 고려해주면 된다.

 

2. 공기청정기가 작동하는데, 위에 공기청정기는 반시계방향, 아래 공기청정기는 시계방향으로 순환한다.

공기청정기로 들어간 미세먼지는 정화된다. 즉, 미세먼지가 사라진다는 뜻이다.

미세먼지는 위 그림과 같이 순환한다.

 

1초마다 이 두 단계가 시행된다, 두 단계가 시행되고 난 후에 남은 미세먼지양을 측정하면 된다.

코드를 살펴보자.

 

사용한 STL과 변수

자료구조 큐 사용을 위한 queue STL, 벡터 사용을 위한 vector STL, 배열 초기화 메서드 memset()를 사용하기위해 cstring STL을 사용했다.

• height, width, checkTime : 입력받는 R, C, T이다.
• pair<int, pair<int, int>>형 큐 q : 맨 앞이 확산되는 양. 뒤 pair가 확산되는 좌표이다.
• airCleanerPoint 벡터 : 공기청정기의 좌표 2개를 저장해두는 벡터이다.
• direction : 상, 우, 하, 좌 방향의 순서대로 확산시키기 위해 더해주는 배열이다.
• board 배열 : 현재 격자칸의 상황을 저장하는 배열이다.
• minusBoard 배열 : 확산이 끝나고 각 칸이 얼마나 확산이 됐는지 더해주는 배열이다. 각 초마다 모든 칸을 0으로 초기화 해줘야 한다.
• ans : 출력하는 값. 남아있는 미세먼지의 양이다.

메인함수

메인함수에서는, 처음에 R, C, T를 입력받는다.

그리고 모든 격자칸의 정보를 입력받는다.

만일 칸이 -1이면, 공기청정기 좌표라는 뜻이므로 airCleanerPoint벡터에 좌표를 저장시켜준다.

 

그리고 go(1초를 의미) 메서드를 호출해서 각 단계를 진행시킨다.

go 메서드는 바로 뒤에 설명하겠다.

 

go메서드가 return되면, 모든 미세먼지의 합을 더해준 후 출력한다.

 

go 메서드

go 메서드는 다음과 같은 구조이다.

위에서 설명한 대로 단계별로 진행된다.

curTime은 지금까지 지난 시간초를 의미한다.

memset() 메서드는 최대 50 x 50개를 초기화하고, 시간은 최대 1,000초 이므로

memset() 메서드로 최대 2,500,000의 시간을 잡아먹는다.

 

나머지의 시간은 메서드를 설명하면서 말해주겠다.

 

확산 가능한 미세먼지 목록 저장하는 메서드

모든 칸을 돌아다니면서 확산 가능한 조건의 칸(미세먼지 양이 5보다 크거나 같은 곳)이 있다면 상, 우, 하, 좌 방향으로 확산을 시도해본다.

만일 해당 방향의 칸이 유효하고, 공기청정기 좌표가 아니라면 확산시킨다.

확산을 저장해두는 큐 q에 저장해두고 확산하는 양만큼 minusBoard에 기록해둔다.

 

모든 칸을 고려하므로 최악의 경우 50 x 50 x 1,000(최대 시간) = 2,500,000의 시간이 이 메서드에서 걸릴 수 있다.

Spread 메서드는 확산시키는 메서드이다.

큐가 비지 않을때까지 모든 확산을 시행한다.

 

후에 확산시킨 곳의 확산한 양만큼 빼기를 해준다.

이 경우 spread() 메서드는 최악의 경우 50 x 50 x 4 (모든 칸에서 확산) x 1,000 = 10,000,000의 시간이 걸리게 되고,

(물론 실제로는 이것보다는 적을 수 밖에 없다.)

minusAfterSpread() 메서드는 50 x 50 x 1,000 = 2,500,000의 시간이 걸리게 된다.

 

위에 공기청정기를 순환하는 메서드 - 1

위에 공기청정기를 순환하는 메서드 - 2

아래 공기청정기를 순환하는 메서드 - 1

아래 공기청정기를 순환하는 메서드 - 2

공기청정기를 순환하는 메서드이다.

어려운 것은 없고, 시작 점을 공기청정기 좌표보다 우측 2번째부터 시작해서

그 이전 칸의 미세먼지를 현재 칸의 미세먼지로 가져오는 것이다.

idx에 맞게 잘 초기화 해주면 된다.

최악의 경우 한 공기청정기를 순환할때마다 200번의 연산을 한다.

 

->최악의 경우 2,500,000 + 2,500,000 + 10,000,000 + 2,500,000 + 200 x 2 의 시간이 소요될 수 있다.

이 문제의 시간제한이 1초이므로 100,000,000 이내로는 무조건 들 수 있었다.

처음에 복사하다가 a가 코드에 적혀져서 오타가 나서 컴파일 에러가 한번 났다..(내 정답률..)

어려운 문제는 아니지만 귀찮다는 평이 많았던 문제다.

 

GitHub - kimyunseok/study-record: my study-record

코드 전문은 위에서 확인이 가능하다.