코드트리 빵

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

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

시원하게 답이 나오지 않는다?

코드가 잘못 됐을 확률이 매우 높다!

새로운 방식을 생각해야한다.

 

제발 문제를 꼼꼼하게 읽어라

사람 이동 다하고 -1 처리 한다는 조건

사람이 움직이고 베이스 캠프 설정하는 조건

 

생각을 해보자.

베이스 캠프 기준으로도 bfs하고

사람을 기준으로도 bfs 하면 함수가 엄청 길어진다. 

 

이 문제의 경우에는

사람이 아닌 편의점을 기준으로 거리를 구하는 것이다.

사람을 기준으로 BFS를 돌리면 시간 초과나고 테스트 케이스 통과 안된다.

왜? 편의점은 고정되어 있기 때문

 

사람의 이동

nagasa 배열로 값을 기준으로

4 방향 값 중 최솟값을 골라 가면 된다.

 

<別解>

베이스 캠프 결정

nagasa 배열 값을 기준으로

이차원 배열 아래(n,n)에서 위(1,1)로 올라가며 고르면 된다.

    int soo = 9999;
    int x = n;
    int y = n;
 
    // 사람 베이스 캠프에 배치
    // 거리가 같다면 행, 열 작은걸로 배치
    for (int i = n; i >= 1; i--)
    {
        for (int j = n; j >= 1; j--)
        {
            if (map[i][j] == 1 && nagasa[i][j] <= soo)
            {
                soo = nagasa[i][j];
                x = i;
                y = j;
            }
        }
    }
 
    // 베이스 캠프에 배치
    people.push_back({ x,y,false });
    // 사람이 들어갔다면 이쪽은 이동 불가능 '-1'
    map[x][y] = -1;

 

<소스 코드>

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <climits>
 
using namespace std;
 
// 상 좌 우 하
int dx[] = { -1, 0, 0, 1 };
int dy[] = { 0, -1, 1, 0 };
 
int jikan = 0;
int n, m;
int map[16][16];
bool visited[16][16];
int nagasa[16][16];
 
struct p_info
{
    int row;
    int col;
    bool arrived;
};
 
struct c_info
{
    int row;
    int col;
};
 
struct b_info
{
    int row;
    int col;
};
 
vector<p_info> people;
vector<c_info> convi;
vector<b_info> basecamp;
 
struct compare_info
{
    int row;
    int col;
    int gili;
};
 
// sort에서는 반대!!
bool operator < (const compare_info& a, const compare_info& b)
{
    if (a.gili == b.gili)
    {
        if (a.row == b.row)
        {
            return a.col < b.col;
        }
        return a.row < b.row;
    }
    return a.gili < b.gili;
}
 
// 편의점을 기준으로 모든 map에 거리를 저장하면서 bfs
void bfs(int s_x, int s_y)
{
    queue<pair<int, int>> q;
    memset(visited, false, sizeof(visited));
    memset(nagasa, 0x3f, sizeof(nagasa));
 
    visited[s_x][s_y] = true;
    q.push(make_pair(s_x, s_y));
    nagasa[s_x][s_y] = 0;
 
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++)
        {
            int nx = x + dx[k];
            int ny = y + dy[k];
 
            if (nx > 0 && nx <= n && ny > 0 && ny <= n)
            {
                if (!visited[nx][ny] && map[nx][ny] != -1)
                {
                    visited[nx][ny] = true;
                    q.push(make_pair(nx, ny));
                    nagasa[nx][ny] = nagasa[x][y] + 1;
                }
            }
        }
    }
}
 
pair<int, int> people_move(int idx)
{
    // 그 사람이 가고싶어하는 "편의점"을 기준으로 bfs
    int a = convi[idx].row;
    int b = convi[idx].col;
    bfs(a, b);
 
    int tmp = 9999;
 
    int f_x = 0;
    int f_y = 0;
    for (int k = 0; k < 4; k++)
    {
        int nx = people[idx].row + dx[k];
        int ny = people[idx].col + dy[k];
        if (nagasa[nx][ny] < tmp)
        {
            tmp = nagasa[nx][ny];
            f_x = nx;
            f_y = ny;
        }
    }
 
    return make_pair(f_x, f_y);
}
 
void simulate()
{
    for (int i = 0; i < people.size(); i++)
    {
        if (people[i].arrived == true)
            continue;
        pair<int, int> tmp = people_move(i);
        people[i].row = tmp.first;
        people[i].col = tmp.second;
    }
 
    for (int f = 0; f < people.size(); f++)
    {
        if (people[f].arrived == true)
            continue;
        if (people[f].row == convi[f].row && people[f].col == convi[f].col)
        {
            // 이제 이 편의점은 지나갈 수 없다.
            map[convi[f].row][convi[f].col] = -1;
            people[f].arrived = true;
        }
    }
 
    // jikan이 사람 수보다 크다면
    // 이제 베이스 캠프에 배치할 사람이 없으므로
    // return;
    if (jikan > m)
        return;
 
    // 사람 배치
    // 편의점을 기준으로 bfs
    bfs(convi[jikan - 1].row, convi[jikan - 1].col);
 
    vector<compare_info> base;
 
    for (int i = 0; i < basecamp.size(); i++)
    {
        if (map[basecamp[i].row][basecamp[i].col] == -1)
            continue;
 
        base.push_back({ basecamp[i].row, basecamp[i].col, nagasa[basecamp[i].row][basecamp[i].col] });
    }
 
    sort(base.begin(), base.end());
    people.push_back({ base[0].row, base[0].col });
    map[base[0].row][base[0].col] = -1;
}
 
bool owari()
{
    for (int i = 0; i < m; i++)
    {
        if (people[i].arrived == false)
            return false;
    }
    return true;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> map[i][j];
            if (map[i][j] == 1)
            {
                basecamp.push_back({ i,j });
            }
        }
    }
 
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        convi.push_back({ a,b });
    }
 
    while (true)
    {
        jikan++;
        simulate();
        if (people.size() == m)
        {
            if (owari())
                break;
        }
    }
    cout << jikan << '\n';
}