문제
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl
풀이
계단 입구까지 이동하고, 대기하고, 내려가는 연산들이 어떤 수학적인 방법으로 쉽게 연산을 할 수 있을 것 같았는데, 도저히 떠오르지 않아서 그냥 1초에 해당하는 위치에 따라 이동하는 것을 모든 사람이 탈출하기 전까지 반복해줬다. 사실 직관적으로 생각해봐도 맵 크기도 별로 크지 않고 사람 수도 상당히 적기 때문에 하나하나 해본다고 해도 시간이 오래걸리지는 않을 것이다. (심지어 계단은 고작 2개 밖에 없다! DFS 조차도 몇번 할 필요가 없다.)
일단 어떤 계단으로 가야 시간이 최소로 걸리는 지 부터 알아야 하는데, 역시 수학적으로 풀 수 있을 것 같지만 그런 방법 따위 생각나지 않으니 그냥 계단 두 개에 한 번씩 들어가게끔 해서 모든 경우의 수를 구해줬다. 어떤 계단으로 갈지 선택했으면 이제 아래의 알고리즘을 따라 만들면 된다.
1. 모든 사람들에 대하여 자신이 갈 계단까지의 거리를 구해서 저장해준다.
2. 특정 조건이 나올 때 까지 반복해준다 :
- 계단 큐를 전부 돌면서 계단을 내려가는 도중인 사람들의 길이를 1 줄여준다.
- 이 때, 계단을 완전히 내려갔으면, 큐에서 빼주고 탈출한 사람을 카운트하는 exit을 1 빼준다.
- 탐색이 끝났으면, 대기 수와 큐의 크기를 확인해서, 대기하는 사람이 있으며 (대기 수가 0보다 크며) 큐의 크기가 3보다 작으면, 큐의 크기가 3이 될 때까지 대기 인원에서 큐로 옮겨준다. (큐에 계단의 길이를 넣어주고, Wait 변수는 1 빼준다.) 이 때, 어차피 시간을 알고 싶은 것이므로 순서는 상관이 없다.
- 계단에 도달하지 않았으면, 거리를 1 빼준다.
- 계단에 도달했으면, 자신이 갈 계단의 번호를 확인해준다.
- 해당 계단의 대기 수를 1 늘려준다.
3. exit = 0 이면, 전부 탈출한 것이므로 연산을 종료해준다.
#include <stdio.h> #include <iostream> #include <vector> #include <math.h> #include <queue> #define MAX 10000000 using namespace std; int map[10][10]; int answer = MAX; void move(vector<pair<int, int> > pos, vector<pair<int, int> > stair, vector<pair<int, int> > select){ vector<int> dist; for(int i = 0; i < select.size(); i++){ int p = select[i].first, st = select[i].second; int px = pos[p].first, py = pos[p].second, sx = stair[st].first, sy = stair[st].second; dist.push_back(abs(px - sx) + abs(py - sy)); } // 이동하는 연산 queue<int> st1, st2; int WaitForst1 = 0, WaitForst2 = 0, time = 0, exit = (int)pos.size(); int visited[11] = { 0, }; while(1){ //cout << WaitForst1 << " " << st1.size() <<'\n'; // 계단을 내려가는 연산 int st1s = (int)st1.size(), st2s = (int)st2.size(); // 1번 계단 // 계단을 내려가는 모든 사람들이 1칸씩 내려가게 한다. for(int i = 0; i < st1s; i++){ // 아직 완전 다 안내려갔으면 다시 큐에 넣어준다. if(st1.front() - 1 > 0) st1.push(st1.front() - 1); // 내려간 사람이 있으면 1명 탈출한다. else if(st1.front() - 1 == 0) exit--; // 탐색한건 빼준다. st1.pop(); } // 해당 큐가 자리가 있으며, 대기 인원이 있으면 if(WaitForst1 > 0 && st1.size() < 3){ // 큐가 다 찰 때까지 대기 인원에서 큐로 인구 이동해준다. while(st1.size() < 3 && WaitForst1 > 0){ st1.push(map[stair[0].second][stair[0].first]); WaitForst1--; } } //////// // 2번 계단 for(int i = 0; i < st2s; i++){ if(st2.front() - 1 > 0) st2.push(st2.front() - 1); else if(st2.front() - 1 == 0) exit--; st2.pop(); } if(WaitForst2 > 0 && st2.size() < 3){ while(st2.size() < 3 && WaitForst2 > 0){ st2.push(map[stair[1].second][stair[1].first]); WaitForst2--; } } ////////// //////////////// // 계단까지 가는 연산 for(int i = 0; i < dist.size(); i++){ // 입구에 도착 안했다면 한칸 더 이동 if(dist[i] > 0) dist[i]--; // 입구에 도착했다면 if(dist[i] == 0 && visited[i] == 0){ // 어떤 계단을 택했었는지 확인 int stn = select[i].second; visited[i] = 1; // 1번 계단이면 : 대기 수 1 증가 (어차피 위에서 대기 인원 만큼 빼주기 때문에 굳이 여기서 빼줄 필요는 없다.) if(stn == 0) WaitForst1++; // 2번 계단이면 : 대기 수 1 증가 else if(stn == 1) WaitForst2++; } } // 1초 경과 time++; // 전부 탈출 했으면 종료 if(exit == 0) break; } answer = min(answer, time); } void DFS(int idx, vector<pair<int, int> > pos, vector<pair<int, int> > stair, vector<pair<int, int> > select){ if(idx == pos.size()){ move(pos, stair, select); return; } select.push_back(make_pair(idx, 0)); DFS(idx + 1, pos, stair, select); select.pop_back(); select.push_back(make_pair(idx, 1)); DFS(idx + 1, pos, stair, select); } int main(){ int T; cin >> T; for(int test_case = 1; test_case <= T; test_case++){ vector<pair<int, int> > pos; vector<pair<int, int> > stair; vector<pair<int, int> > select; int n; cin >> n; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ cin >> map[i][j]; if(map[i][j] == 1) pos.push_back(make_pair(j, i)); else if(map[i][j] > 1) stair.push_back(make_pair(j, i)); } } DFS(0, pos, stair, select); cout << "#" << test_case << " " << answer << '\n'; pos.clear(); stair.clear(); select.clear(); answer = MAX; } return 0; }
댓글
댓글 쓰기