코드트리 - 코드트리 빵

코드트리 빵

코드트리 Gold 2 Simulation BFS
코드트리 - 코드트리 빵

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

 

문제 풀이

m 명의 사람이 본인의 번호과 동일한 시간에 맵에 입장하게 된다.
이 조건만 좀 신경써주면 금방 풀리는 문제였다.

 

모든 사람은 각각의 목적지를 가지는데, 목적지를 기준으로 BFS를 이용해 가장 가까운 베이스 캠프를 찾아 배정해줬다.
베이스캠프에서 편의점으로 가는 방식 또한 우선순위 대로 BFS를 통해 편의점으로 가는 최단거리 방향으로 한칸 씩 이동시켜 줬다.

모든 사람은 각각 원하는 편의점에 도달할 수 있다 가정해도 된다 했으므로, 못찾는 경우는 고려하지 않았다.

 

시간과 사람이 몇명 들어갔는 지만 좀 신경써주면 되는 문제였는데,
사람을 움직이는 함수에서 시간보다 높은 숫자가 들어오게 되면 즉시 함수를 종료 시켰다.

 

사람들의 이동을 체크하고 도달했다면 해당 편의점을 벽으로 막아주는 작업 역시,
현재 시간 보다 높은 숫자를 가지는 사람은 신경쓰지 않고 진행했다.

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct person {
    int x, y, gx, gy;
    bool isArrive;

    person() : x(0), y(0), gx(0), gy(0), isArrive(false) {}
};

int n, m, t=1;
int mv[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
vector<vector<int>> fld;
vector<person> pInfo;

void findBaseCamp() {
    vector<vector<bool>> visited(n, vector<bool>(n, false));
    queue<pair<int, int>> q;
    pair<int, int> res = make_pair((n)*100+n, n*n);

    visited[pInfo[t].gx][pInfo[t].gy] = true;
    q.push(make_pair(pInfo[t].gx*100+pInfo[t].gy, 0));

    while (!q.empty()) {
        int x = q.front().first/100;
        int y = q.front().first%100;
        int dist = q.front().second; q.pop();

        for (int dir=0; dir<4; dir++) {
            int dx = x + mv[dir][0];
            int dy = y + mv[dir][1];

            if (dx < 0 || dx >= n || dy < 0 || dy >= n) continue;
            if (fld[dx][dy] > 1 || visited[dx][dy]) continue;

            // 베이스캠프를 찾았을 경우
            if (fld[dx][dy] == 1) {
                // 거리가 더 짧으면 바꿈
                if (dist < res.second) {
                    res = make_pair(dx*100+dy, dist);
                }
                // 같은 거리에 있으면 우선순위에 따라 교체
                else if (dist == res.second) {
                    if (res.first/100 > dx) res = make_pair(dx*100+dy, dist);
                    else if (res.first/100 == dx && res.first%100 > dy) res = make_pair(dx*100+dy, dist);
                }
            }
            visited[dx][dy] = true; 
            q.push(make_pair(dx*100+dy, dist+1));

        }
    }

    pInfo[t].x = res.first/100;
    pInfo[t].y = res.first%100;
    fld[res.first/100][res.first%100] = 2;
    return ;
}

bool setWall () {
    int cnt = 0;
    for (int i=1; i<pInfo.size(); i++) {
        if (t <= i) continue;
        if (pInfo[i].isArrive) {
            cnt++;
            continue;
        }

        if (pInfo[i].x == pInfo[i].gx && pInfo[i].y == pInfo[i].gy) {
            cnt++;
            pInfo[i].isArrive = true;
            fld[pInfo[i].x][pInfo[i].y] = 2;
        }
    }

    if (cnt == m) return true;
    return false;
}

void movingPeople (int num) {
    if (num > m || num > t) return;

    vector<vector<bool>> visited(n, vector<bool>(n, false));
    queue<pair<int, int>> q;
    // dx,dy, dir
    q.push(make_pair(pInfo[num].x*100+pInfo[num].y, 5));

    visited[pInfo[num].x][pInfo[num].y] = true;

    while (!q.empty()) {
        int x = q.front().first/100;
        int y = q.front().first%100;
        int dir = q.front().second; q.pop();

        for (int i=0; i<4; i++) {
            int dx = x + mv[i][0];
            int dy = y + mv[i][1];

            if (dx < 0 || dx >= n || dy < 0 || dy >= n) continue;
            if (fld[dx][dy] == 2 || visited[dx][dy]) continue;

            // 도착하면
            if (dx == pInfo[num].gx && dy == pInfo[num].gy) {

                dir = dir > 3 ? i : dir;

                pInfo[num].x += mv[dir][0];
                pInfo[num].y += mv[dir][1];
                return ;
            }
            q.push(make_pair(dx*100+dy, dir > 3 ? i : dir));
            visited[dx][dy] = true;
        }
    }
}

int main () {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    cin >> n >> m;

    fld.resize(n, vector<int>(n, 0));

    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            cin >> fld[i][j];
        }
    }

    // 1번 부터 1번 사람
    person tmp;
    pInfo.push_back(tmp);

    for (int i=0; i<m; i++) {
        cin >> tmp.gx >> tmp.gy;
        tmp.gx--;
        tmp.gy--;
        pInfo.push_back(tmp);
    }

    findBaseCamp(); t++;

    while (true) {
        for (int i=1; i<=m; i++) {
            if (pInfo[i].isArrive) continue;
            movingPeople(i);
        } 

        if (setWall()) break;

        if (t <= m) {
            findBaseCamp();
        }
        t++;
    }

    cout << t << "\n";

    return 0;
}

회고

처음에 코드가 두번 되고 한번 segmentation fault 가 나길래 뭐지 하면서 계속 해서 돌려봤었는데, 시간에 따른 사람 번호에 대한 조건을 빠뜨려서 문제였다.

이런 실수는 줄이도록 해야 할 듯.