A. 문제설명
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl
문제에 대한 자세한 설명은 링크 참조
1. 크기가 N×N인 지도가 존재
2. P로 표시된 각 좌표에 사람들이 위치하고, S로 표시된 위치에 계단이 존재
3. 계단에는 한번에 3명의 사람들만 들어갈 수 있고, 계단의 길이는 입력으로 주어지며 그 길이만큼 내려가는 시간이 소요
4. 모든 사람들을 각 계단에 배치하여 내려가게 할 때, 마지막 사람까지 모두 계단을 내려가는 최소의 시간을 구하라
B. 접근법
DFS + 시뮬레이션
우선 계단1/2에 대한 사람들의 선택에 대한 조합을 먼저 DFS로 구한다.
그 후, 각 계단을 선택한 사람들이 계단을 내려가는 시뮬레이션을 문제의 조건에 충실히 구현하면 되는데, 여기서 주의할 점은 1. 각 계단에 진입 이전 대기할 때 1초가 소요되고 2. 계단에 나가는 동시에 대기하는 인원이 들어올 수 있고 3. 계단에는 시간과 공간만 가용하다면 한번에 여러명이 들어가고 나갈 수 있다.
위 세 조건에 맞추어 대기큐와 계단큐를 따로 구현하여 시뮬레이션했는데, 문제 정의가 모호하여 해당 조건을 이해하는데 조금 시간이 걸렸다.
C. 풀이
1. DFS로 계단1/2에 대한 조합을 모두 구함
2. 구해진 조합으로 계단 시뮬레이션 수행
2-1. waitQ에는 각 계단별 대기자가 삽입됨(도착한 순서대로): 실제 구현은 우선순위 큐 사용
2-2. 먼저 삽입된 대기자들 순으로 모든 waitQ와 strQ가 빌때까지 무한루프
2-3. tick을 하나씩 증가시키며 strQ가 비어있을 경우 waitQ의 대기자를 빼고 그를 strQ에 넣음
2-4. 여기서 waitQ의 대기자는 tick보다 1 크거나 같아야만 계단에 진입가능
3. 위 루프를 계단큐와 대기큐의 인원이 전부 내려갈 때까지 수행
4. 최소의 시간을 계속 업데이트
D. 내 코드
