문제 링크 : https://www.acmicpc.net/problem/20056
SW17144 미세먼지 안녕! 과 비슷한 유형의 문제였다.
문제의 핵심은
- 파이어볼을 이동시킨다.
- 이동시킨 곳의 파이어볼들을 합치고 새로운 파이어볼들을 만든다.
- 1~2과정을 주어진 횟수만큼 반복한다.
이다.
문제의 접근 방법은 위와 같이 매우 간단하기 때문에 시간을 줄인 방법에 대해서도 다뤄보고자 한다.
1.
2개의 Queue로 이전 파이어볼들이 마지막으로 도착한 장소의 위치와
이전 파이어볼들로 인해서 발생한 or 합쳐지지 않은 파이어볼들을 각각 관리해주었다.
파이어볼의 관리를 그렇다 하더라도 파이어볼이 마지막에 도착한 장소 위치를 저장하면
모든 장소를 순회할 필요가 없기 때문에 조금 더 효유적이라고 생각했다.
Queue는 시,공간 복잡도 모두 좋지 않지만 직관적이고 불필요한 오류를 발생시키지 않아서 적용했다.
Queue 대신 N차원 배열에 저장하고 첨자관리를 하면 메모리와 시간을 더 아낄 수 있다.
2.
전역변수로 변수들을 관리했다. 첫번째 제출에서 반복문 내에 int[][][] a = new int[N+2][N+2][5];같은 코드를 작성했다.
이 코드의 제출 결과, 메모리와 시간 모두 좋지 못했고 이것을 개선하고자
다음과 같이 모든 변수를 전역으로 관리하니 가장 짧은 시간이 나왔다.
다만 잘돌아가던 지역 변수를 전역 변수로 바꾸니 없던 에러가 발생하고 테케도 틀리는 경우가 발생했기 때문에 통과하기 전에는
지역변수로 관리가 가능한 변수는 지역에서만 사용하는 것이 좋으리라 생각했다.
3.
fastio를 사용한다.
다음으로 코드와 코드 진행순서만 작성하겠다.
각 파이어볼의 속성을 넣은 int형 배열을 q에 삽입한다.
각 차례마다 존재하는 모든 파이어볼을 순회하며 이동시킨다.
3차원 배열을 사용해서 파이어볼의 도착 좌표 위치에 파이어볼의 데이터를 모두 넣는다.
이 때 대각선으로 흩어질 것인지 가로 세로로 흩어질 것인지도 판별한다.
그리고 효율적으로 탐색하기 위해 파이어볼이 1개라도 저장된 좌표를 저장하는 Q에 저장한다.
좌표가 저장된 Queue를 순회하며 해당 좌표에 파이어볼이 1개있다면 그대로 내버려두고
2개 이상 있다면 파이어볼을 조각내거나 소멸하는 작업을 진행한다.
조각낸 파이어볼은 또 다시 파이어볼이 저장된 Queue에 저장되어 다음 차례에 움직이거나 모든 차례를 마쳤을 경우 남은 질량을 계산하고 정답을 출력한다.
