SWEA 2383번 - 점심 식사시간

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번 작업으로 돌아가 다른 계단을 지정해줄 때 시간을 구해준다.

#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;
}