[SW Expert Academy] 2383. 점심 식사시간

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<functional>
#include<algorithm>
#define p pair<int,int>
using namespace std;

int n;
int ans;
int map[11][11];

struct Node{
    int x;
    int y;
    int target;
    int value;
    Node(int _x, int _y) : x(_x), y(_y) {};
    Node(int _x, int _y, int _value) : x(_x), y(_y), value(_value){};
};
vector<Node> n_v; // n_v is node vector
vector<Node> s_v; // s_v is stair vector

int distance(int n_idx, int s_idx){
    int x = abs(n_v[n_idx].x - s_v[s_idx].x);
    int y = abs(n_v[n_idx].y - s_v[s_idx].y);
    return x + y ;
}

void dfs(int idx){
    if(idx == n_v.size()){
        int people_cnt = (int) n_v.size();
        int time = 0;
        int exit_cnt = 0;
        
        queue<int> waiting[2];
        queue<int> stair[2];
        
        // 각자 원하는 계단으로 가기 위한 거리 계산
        for(int i=0; i<people_cnt; i++){
            int dis = distance(i, n_v[i].target);
            waiting[n_v[i].target].push(dis);
        }
        
        /*
         작업 순서
         1. time++
         2. 계단에 있는 인원 내려가기
         3. 계단에 인원 추가하기
         */
        while (exit_cnt < people_cnt) {
            time ++;
            
            // 계단에 있는 인원 내려가기
            for(int i=0; i<2; i++){
                int size = (int) stair[i].size();
                for(int j=0; j<size; j++){
                    int top = stair[i].front();
                    stair[i].pop();
                    top--;
                    if(top != 0)
                        stair[i].push(top);
                    else
                        exit_cnt++;
                }
            }
            
            // 계단에 인원 추가하기
            for(int i=0; i<2; i++){
                int size = (int) waiting[i].size();
                for(int j=0; j<size; j++){
                    int dis = waiting[i].front();
                    waiting[i].pop();
                    dis--;
                    if(dis <= 0){
                        if(stair[i].size() < 3){ // 계단에 도착했지만 내려가는 인원이 Full
                            stair[i].push(s_v[i].value);
                        }
                        else{
                            waiting[i].push(dis);
                        }
                    }
                    else{
                        waiting[i].push(dis);
                    }
                }
            }
        } // end of while
        /*
        ans 구할 때
        time + 1해주는 이유
        000
        130
        000 과 같이 주어졌다고 가정하자.

        내 로직대로라면
        time : 1초 
        3번 작업 수행 --> stair에 push

        time : 2초
        2번 작업 수행 --> 남은 시간 2초

        time : 3초
        2번 작업 수행 --> 남은 시간 1초

        time : 4초
        2번 작업 수행 --> 남은 시간 0초

        이렇게 while문을 탈출한다.

        그런데 이때 답은 4초가 아닌 5초를 출력해야한다.
        그래서 while문을 탈출한 시간(=time)에 +1를 해준다.
        */
        ans = ans < time+1 ? ans : time+1;
    } // end of if
    else {
        for(int i=0; i<2; i++){
            n_v[idx].target = i;
            dfs(idx+1);
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int TC;
    cin >> TC;
    
    for(int tc=1; tc<=TC; tc++){
        memset(map,0,sizeof(map));
        n_v.clear();
        s_v.clear();
        cin >> n;
        ans = 2e9;
        
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                int tmp;
                cin >> tmp;
                if(tmp == 1)
                    n_v.push_back(Node(i,j));
                else if( tmp > 1)
                    s_v.push_back(Node(i,j,tmp));
            }
        }
        dfs(0);
        cout << "#" << tc << " " << ans << '\n';
    }
}

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define p pair<int,int>
using namespace std;

int n,ans;
int map[10][10];
int dir[10];
vector<p> pos_stairs; // position of stairs
vector<int> time_stairs;
vector<p> pos_people; // position of people

void solve(){
    int time = 0;
    int size = (int) pos_people.size();
    int to_exit_people = size;
    
    vector<int> people;
    queue<int> stairs[2];
    
    // 각 사람마다 목표 계단까지의 거리 구하기
    for(int i=0; i<size; i++){
        int _x, _y;
        _x = abs(pos_people[i].first - pos_stairs[dir[i]].first);
        _y = abs(pos_people[i].second - pos_stairs[dir[i]].second);
        people.push_back(_x+_y+1); // 도착 후 1분이 지나야 내려갈 수 있기 때문에 +1
    }
    
    while (to_exit_people) {
        time++;
        
        for(int i=0; i<size; i++){
            // [1]
            if( people[i] == -1 )
                continue;
                // people[i] - 1 == 0 은 1초 후 계단으로 내려갈 수 있는 사람
                // people[i] == 0 은 바로 내려갈 수 있는데 계단이 Full이라서 못내려가는 사람
            else if(people[i] - 1 == 0 || people[i] == 0){
                if( stairs[ dir[i] ].size() < 3){
                    stairs[ dir[i] ].push(time_stairs[ dir[i] ]);
                    people[i] = -1;
                }
            }
            else{
                people[i] --;
            }
            /*                 
            //[2]
            if(people[i] == -1 )
                continue;
            else if(people[i] == 0){
                if( stairs[ dir[i] ].size() < 3){
                    stairs[ dir[i] ].push(time_stairs[ dir[i] ]);
                    people[i] --;
                }
            }
            else {
                people[i] --;
                if( people[i] ==0 && stairs[ dir[i] ].size() < 3){
                    stairs[ dir[i] ].push(time_stairs[ dir[i] ]);
                    people[i] --;
                }
            }
            */
        }

        int queue_size = (int) stairs[0].size();
        while (queue_size--) {
            int top = stairs[0].front();
            stairs[0].pop();
            top --;
            if(top == 0)
                to_exit_people--;
            else{
                stairs[0].push(top);
            }
        }
        
        queue_size = (int) stairs[1].size();
        while (queue_size--) {
            int top = stairs[1].front();
            stairs[1].pop();
            top --;
            if(top == 0)
                to_exit_people--;
            else{
                stairs[1].push(top);
            }
        }
        
    } // end of While
    ans = ans > time ? time : ans;
}

void dfs(int idx){
    if(idx == pos_people.size()){
        solve();
    }
    else{
        for(int i=0; i<2; i++){
            dir[idx] = i;
            dfs(idx+1);
        }
    }
}

int main(){
    int TC;
    cin >> TC;
    for (int tc=1; tc<=TC; tc++) {
        cin >> n;
        ans = 2e9;
        memset(map,0,sizeof(map));
        memset(dir,0,sizeof(dir));
        pos_stairs.clear();
        time_stairs.clear();
        pos_people.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)
                    pos_people.push_back({i,j});
                else if(map[i][j] > 1){
                    pos_stairs.push_back({i,j});
                    time_stairs.push_back(map[i][j]);
                }
            }
        }
        dfs(0);
        
        printf("#%d %d\n",tc, ans+1);
    } // end of for tc
    return 0;
}