[코드트리] 코드트리 빵 (C++)

[문제]

https://www.codetree.ai/training-field/frequent-problems/problems/codetree-mon-bread/description?page=1&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

[설명]

빡구현 문제 중 쉬운편인가... 처음으로 1시간30분만에 풀었다...!구조체 벡터를 사용한 뒤로 계속 사용하고있는데, 이번에도 역시 사람들의 좌표, 보드내부에 있는지 여부, 도착했는지 여부를 정보로 하는 구조체를 만들고, 벡터로 만들어 관리해주었다.

 

구현 순서는 이렇게했다.1. 종료 조건 설정구조체 벡터를 탐색하여 out상태인 person수를 새어 전체 person수와 동일하면 반복문 탈출

 

2. base 탐색base를 탐색할 차례의 person의 도착지로 부터 BFS를 돌렸다.base들중 가장 낮은 거리를 가진 최단거리를 min_dis 변수에 저장한뒤, board를 순차 탐색해 제일 먼저 발견되는 min_dis 좌표를 들어갈 base로 설정하였다. 이렇게 행, 열 조건에따른 우선순위를 맞출 수 있다. 들어갈 base를 정하면 board에서 지나가지 못하게 base좌표를 -1로 예외처리해준다. 

 

3. 사람 움직임 여기서 가장 시간이 걸리긴 했는데, 전에 사용했던 역BFS 탐색을 사용했다. - 먼저 사람으로 부터 BFS를 하여, 다음 좌표에 이전 좌표를 저장한다.- 도착지에 BFS 도달시 종료하며, 도착지로부터 이전좌표를 따라간다.- 현재 위치에 도달하면 해당 사람에게 자신의 온좌표를 넘겨준다. 이방식을 사용하면 우선순위를 지키며 최적의 경로의 좌표를 사람에게 줄 수 있다.

 

4. 편의점 도착시 모든 사람이동한후, 편의점 도착 처리가 필요하다. 따라서 위의 3번과정을 진행할때 해당 사람이 도착지에 도착한 경우 사람이 도착한것을 구조체의 out정보에 기록하고, 이동이 종료된후 모든 사람을 순차탐색하며, out된 사람인경우 board에서 도착지를 -1로 맵핑했다.   

 

#include <bits/stdc++.h>

using namespace std;
#define X first
#define Y second
int dx[4] = {-1,0,0,1};
int dy[4] = {0,-1,1,0};

int N, M;
int board[16][16];

struct person{
    int num;
    int x,y;
    int des_x, des_y;
    bool in;
    bool out;
};

vector <person> persons;
vector <pair<int,int>> bases;
void find_base(person me){ //BFS
    queue <pair<int,int>> q;
    int dis[16][16] = {0,};
    q.push({me.des_x, me.des_y});
    while(!q.empty()){
        pair <int, int> cur = q.front();
        q.pop();
        dis[me.des_x][me.des_y] = 1;
        for(int i = 0; i < 4; i++){
            int nx = cur.X + dx[i];
            int ny = cur.Y + dy[i];
            if(dis[nx][ny]!=0) continue;
            if(nx < 0||nx>=N||ny<0 || ny>=N) continue;
            if(board[nx][ny] < 0) continue; //베이스 들어간 경우 혹은 편의점 들어간 경우

            dis[nx][ny] = dis[cur.X][cur.Y] + 1;
            q.push({nx,ny});
        }
    }

    int min_dis = 1000;
    for (int i = 0; i < bases.size(); ++i) {

        if (board[bases[i].X][bases[i].Y] == 1 && dis[bases[i].X][bases[i].Y] != 0) //유효한 베이스
            min_dis = min(min_dis, dis[bases[i].X][bases[i].Y]); //가장 가까운 거리
    }
    for (int j = 0; j < N; ++j) {
        for (int k = 0; k < N; ++k) {
            if(min_dis == dis[j][k] && board[j][k] == 1) {
                me.x = j; //내좌표갱신.
                me.y = k;
                board[j][k] = -1;
                me.in = true;
                persons[me.num] = me;
                return;
            }
        }
    }
}

void person_move(person me){
    bool vis[16][16] = {0,};
    int dis_x[16][16] = {0,};
    int dis_y[16][16] = {0,};
    bool end_flag = false;
    queue <pair<int,int>> q;
    q.push({me.x, me.y});
    vis[me.x][me.y] = true;
    while(!q.empty()){
        pair <int, int> cur = q.front();
        q.pop();

        for(int i = 0; i < 4; i++){
            int nx = cur.X + dx[i];
            int ny = cur.Y + dy[i];
            if(vis[nx][ny]) continue;
            if(nx < 0||nx>=N||ny<0 || ny>=N) continue;
            if(board[nx][ny] < 0) continue; //베이스 들어간 경우 혹은 편의점 들어간 경우

            vis[nx][ny] = true;
            dis_x[nx][ny] = cur.X;
            dis_y[nx][ny] = cur.Y;
            q.push({nx,ny});
            if(nx == me.des_x && ny == me.des_y) {
                end_flag = true;
                break;
            }
        }
        if(end_flag) break;
    }
    //back_BFS;
    pair <int, int> cur = {me.des_x, me.des_y};
    while(true){
        int nx = dis_x[cur.X][cur.Y];
        int ny = dis_y[cur.X][cur.Y];
        if(nx == me.x && ny == me.y){

            me.x = cur.X;
            me.y = cur.Y; //다음 좌표 갱신.
            if(me.x == me.des_x && me.y == me.des_y){
                me.out = true;
                me.in = false;
            }
            persons[me.num] = me;
            break;
        }
        cur = {nx, ny};
    }
}


int main() {
    cin >> N >> M;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> board[i][j];
            if (board[i][j] == 1)
                bases.push_back({i, j});
        }
    }
    int x, y;
    persons.push_back({0, 0, 0, 0, 0, false, false});
    for (int i = 1; i <= M; ++i) {
        cin >> x >> y; //편의점 좌표
        persons.push_back({i, 0, 0, x - 1, y - 1, false, false});
    }
    int time = 1;

    while (true) {
        for (int i = 1; i <= M; i++) {
            {
                if (persons[i].in) person_move(persons[i]);

            }
        }

        for (int i = 0; i <= M; ++i) {
            if (persons[i].out)
                board[persons[i].des_x][persons[i].des_y] = -1; //다이동한후에 이동할 수 없도록.
        }

        if (time <= M) //시간이 사람수 보다 작을때만
            find_base(persons[time]); //3번


        int count = 0;
        for (int i = 1; i <= M; i++) {
            if (persons[i].out)
                count++;
        }
        if (count == M) break;//전부 나간 경우 종료

        time++;

    }
    cout << time;

}