https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl
처음에 문제를 보고 1시간 동안 어떻게 풀까 고민했었다.
상하좌우 이동을 할 때마다 모든 경우를 DFS로 돌리자니 너무 복잡해 질거 같아서 고민을 하다가
계단이 오직 2가지 밖에 없고 N이 10 이하인 점을 보고 미리 계단 수를 지정할 수 있도록 접근했다.
다행히 pass를 하였지만, N제한과 계단의 수가 늘어났을 때 어떻게 풀어야할지는 더 고민을 해봐야 할 것 같다.
먼저 접근 방향은 다음과 같다.
1) 사람마다 어떤 계단으로 갈지를 DFS 함수를 통해 지정한다. (1번 계단/2번 계단)
2) 모든 사람의 계단을 지정했다면 지정한 계단과의 거리 값을 구한 뒤에 이동을 시작한다.
3) 만약 계단에 도착하고 아무도 없다면 계단에서의 이동을 시작한다.
4) 계단에 도착했지만 3명 이상이 이동을 하고 있다면, 대기해준 뒤에 다시 3번 작업을 반복한다.
5) 위의 작업을 마쳤다면, 다시 1번 작업으로 돌아가 다른 계단을 지정해줄 때 시간을 구해준다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 | #include <iostream> #include <vector> #include <queue> #include <math.h> using namespace std; int N; int ans=0; vector<vector<int>> map; vector<pair<int,int>> person_location; //방 안의 사람들 위치 vector<pair<int,int>> stair_location; //계단 위치 vector<int> person_stair; //방 안의 사람들이 선택한 계단 번호 (1,2) int move(){ int n=(int)person_location.size(); // 사람 수 int finish=0; //완료된 사람 int total_time=0; queue<int> q[2]; //계단에 있는 사람들 남은 시간 vector<int> dist(n,0); for(int i=0;i<n;i++){ int y=person_location[i].first; //현재 y좌표 int x=person_location[i].second; //현재 x좌표 int sy=stair_location[person_stair[i]].first; //선택한 계단 y좌표 int sx=stair_location[person_stair[i]].second; //선택한 계단 x좌표 dist[i]=abs(y-sy)+abs(x-sx); } while(true){ if(finish==n) break; for(int i=0;i<n;i++){ if(dist[i]<0) continue; if(dist[i]==0){ //계단 위치 if(q[person_stair[i]].size()<3){ int sy=stair_location[person_stair[i]].first; //선택한 계단 y좌표 int sx=stair_location[person_stair[i]].second; //선택한 계단 x좌표 q[person_stair[i]].push(map[sy][sx]); dist[i]=-1; } continue; } dist[i]-=1; } //계단에 있는 사람들 이동 for(int i=0;i<2;i++){ int cnt=(int)q[i].size(); for(int j=0;j<cnt;j++){ int t=q[i].front(); q[i].pop(); if(t>1) q[i].push(t-1); else finish++; } } total_time++; } return total_time+1; } void dfs(int pos){ if(pos==person_location.size()){ ans=min(ans,move()); return; } person_stair[pos]=0; //1번 계단 dfs(pos+1); person_stair[pos]=1; //2번 계단 dfs(pos+1); return; } int main(){ int T; cin>>T; for(int testCase=1;testCase<=T;testCase++){ scanf("%d",&N); map=vector<vector<int>> (N,vector<int>(N,0)); ans=99999999; person_location.clear(); stair_location.clear(); for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ scanf("%d",&map[i][j]); if(map[i][j]==1) person_location.push_back(make_pair(i,j)); else if(map[i][j]>1) stair_location.push_back(make_pair(i,j)); } } person_stair=vector<int> (person_location.size(),0); dfs(0); printf("#%d %d\n",testCase,ans); } return 0; } | cs |
'알고리즘(SWEA) > 시뮬레이션' 카테고리의 다른 글
| SWEA 5644번 - 무선충전 (0) | 2019.10.09 |
|---|---|
| SWEA 5650번 - 핀볼게임 (0) | 2019.09.01 |