[코드트리] 코드트리빵 - 시뮬레이션 (기출문제)

삼성 SW 역량테스트 2022 하반기 기출

코드트리빵

최근 코드트리 빵이 전국적으로 인기를 얻어 편의점에서 해당 빵을 구하기 힘들어졌습니다. 빵을 구하고자 하는 m명의 사람이 있는데, 1번 사람은 정확히 1분에, 2번 사람은 정확히 2분에, ..., m번 사람은 정확히 m 분에 각자의 베이스캠프에서 출발하여 편의점으로 이동하기 시작합니다. 사람들은 출발 시간이 되기 전까지 격자 밖에 나와있으며, 사람들이 목표로 하는 편의점은 모두 다릅니다. 이 모든 일은 n*n 크기의 격자 위에서 진행됩니다.

코드트리 빵을 구하고 싶은 사람들은 다음과 같은 방법으로 움직입니다. 이 3가지 행동은 총 1분 동안 진행되며, 정확히 1, 2, 3 순서로 진행되어야 함에 유의합니다.

1. 격자에 있는 사람들 모두가 본인이 가고 싶은 편의점 방향을 향해서 1 칸 움직입니다. 최단거리로 움직이며 최단 거리로 움직이는 방법이 여러가지라면 ↑, ←, →, ↓ 의 우선 순위로 움직이게 됩니다. 여기서 최단거리라 함은 상하좌우 인접한 칸 중 이동가능한 칸으로만 이동하여 도달하기까지 거쳐야 하는 칸의 수가 최소가 되는 거리를 뜻합니다.
2. 만약 편의점에 도착한다면 해당 편의점에서 멈추게 되고, 이때부터 다른 사람들은 해당 편의점이 있는 칸을 지나갈 수 없게 됩니다. 격자에 있는 사람들이 모두 이동한 뒤에 해당 칸을 지나갈 수 없어짐에 유의합니다.
3. 현재 시간이 t분이고 t ≤ m를 만족한다면, t번 사람은 자신이 가고 싶은 편의점과 가장 가까이 있는 베이스 캠프에 들어갑니다. 여기서 가장 가까이에 있다는 뜻 역시 1에서와 같이 최단거리에 해당하는 곳을 의미합니다. 가장 가까운 베이스캠프가 여러 가지인 경우에는 그 중 행이 작은 베이스캠프, 행이 같다면 열이 작은 베이스 캠프로 들어갑니다. t번 사람이 베이스 캠프로 이동하는 데에는 시간이 전혀 소요되지 않습니다.
4. 이때부터 다른 사람들은 해당 베이스 캠프가 있는 칸을 지나갈 수 없게 됩니다. t번 사람이 편의점을 향해 움직이기 시작했더라도 해당 베이스 캠프는 앞으로 절대 지나갈 수 없음에 유의합니다. 마찬가지로 격자에 있는 사람들이 모두 이동한 뒤에 해당 칸을 지나갈 수 없어짐에 유의합니다.

(중략)

 

입력 형식

첫 번째 줄에는 격자의 크기 n과 사람의 수 m이 공백을 사이에 두고 주어집니다.

이후 n개의 줄에 걸쳐 격자의 정보가 주어집니다. 각 줄에 각각의 행에 해당하는 n개의 수가 공백을 사이에 두고 주어집니다.
0의 경우에는 빈 공간, 1의 경우에는 베이스캠프를 의미합니다.

이후 m개의 줄에 걸쳐 각 사람들이 가고자 하는 편의점 위치의 행 x, 열 y의 정보가 공백을 사이에 두고 주어집니다.

각 사람마다 가고 싶은 편의점의 위치는 겹치지 않으며, 편의점의 위치와 베이스캠프의 위치도 겹치지 않습니다.

• 2 ≤ n ≤ 15
• 1 ≤ m ≤ min(n2,30)
• m ≤ 베이스 캠프의 개수 ≤ n2−m

출력 형식

모든 사람이 편의점에 도착하는 시간을 출력하세요.

문제 조건에 의해 어떠한 사람이 원하는 편의점에 도달하지 못하게 되는 경우는 절대 발생하지 않음을 가정해도 좋습니다.
또한, 이동하는 도중 동일한 칸에 둘 이상의 사람이 위치하게 되는 경우 역시 가능함에 유의합니다.

---

 

한시간동안 겨우 step3만 구현해놓고

너무 오래 걸리기도 했고

우선순위 좌표 때문에 bfs를 편의점부터 탐색하는게 맞나 싶어서 해설 풀이를 참고했다

 

결론은 내 방법이 맞았음

그리고 사람(people) 좌표와 편의점(store) 좌표를 pair로 저장해놓으면

나중에 각각 인덱스로 비교하기 편하다는 걸 발견해서 그것도 써먹었다!

 

또한 처음 제출에서 시간초과가 났는데

알고보니 step3 과정에서 findCamp 함수에 문제가 있었다.

사실 정확한 이유는 모르겠지만 풀이랑 비교를 해보니

if(visited[i][j] && campMap[i][j] == 1) 여기서 visited 조건을 추가하지 않으면 시간초과가 일어남.

 

+

why?

사람이 있던 캠프(못 지나가는 칸)를 BFS 과정 중 visited에서 걸렀으니까, findCamp에서도 이를 걸러야 함!!

그래서 visited[i][j] 를 확인하거나, campMap[i][j] != 9 조건을 추가했어야 했던 것이다

세상에...이런거 조건 하나하나 따지면서 잘 생각해야겠다ㅠ

 

 

 

나의 풀이

#include <iostream>
#include <queue>
using namespace std;

int n;
int m;
int campMap[16][16];
pair<int,int> store[226];
int finish[226];
int timer = 0;
queue<pair<int,int>> q;
int dx[4] = {-1,0,0,1}; // 우선순위대로
int dy[4] = {0,-1,1,0};
pair<int,int> people[226];
int visited[16][16]={0};
int step[16][16] = {0};

void findCamp(int person){
    // 캠프 위치 & step 최솟값 찾기
    int minCamp = 500;
    int x; int y;
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=n; ++j){
            if(visited[i][j] && campMap[i][j] == 1){ // visited 추가안해서 시간초과남
                if(step[i][j] < minCamp) {
                    minCamp = step[i][j];
                    x = i; y = j;
                }
            }
        }
    }
    campMap[x][y] = 9;
    people[person] = {x,y};
    // cout << x<<" "<<y<<"\n";
}

void findBFS(pair<int,int> str){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++) {
            visited[i][j] = 0;
            step[i][j] = 0;
        }
    }
    int firstcamp = 0;

    q.push({str.first, str.second});
    visited[str.first][str.second] = 1;
    while(!q.empty()){
        pair<int,int> a = q.front();
        q.pop();
        for(int i=0; i<4; ++i){
            int nx = a.first + dx[i];
            int ny = a.second + dy[i];
            if(nx<1 || ny<1 || nx>n || ny>n) continue;
            if(campMap[nx][ny] == 9) continue; // 사람이 거쳐간 캠프
            if(visited[nx][ny]==1) continue;
            step[nx][ny] = step[a.first][a.second] + 1;
            q.push({nx,ny});
            visited[nx][ny] = 1;
        }
    }
    
}

void movePeople(){
    // step 1
    for(int i=1; i<=m; ++i){
        if(people[i] == make_pair(-1,-1) || people[i] == store[i]) continue;
        findBFS(store[i]);

        int px = people[i].first;
        int py = people[i].second;
        int mx = 0; int my = 0;
        int mindist = 500;
        for(int j=0; j<4; ++j){ // 이동할 위치 찾기
            int nx = px + dx[j];
            int ny = py + dy[j];
            if(nx<1 || ny<1 || nx>n || ny>n) continue;
            if(campMap[nx][ny] == 9) continue;
            if(visited[nx][ny] && mindist > step[nx][ny]){
                mindist = step[nx][ny];
                mx = nx; my = ny;
            }
        }
        people[i] = {mx, my};

        // step 2
        if(people[i] == store[i]){
            campMap[people[i].first][people[i].second] = 9;
            finish[i] = 1;
        }

    }
    // step 3
    if(timer > m) return;
    
    findBFS(store[timer]);
    findCamp(timer);

}

int main() {
    int x; int y;
    cin>>n>>m;
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=n; ++j){
            cin>>campMap[i][j];
        }
    }
    for(int i=1; i<=m; ++i){
        cin >> x >> y;
        store[i] = {x,y};
    }

    for(int i = 1; i <= m; i++){
        people[i] = {-1,-1};
    }
    while(1){
        timer++;
        movePeople();
        bool stop = true;
        for(int i=1; i<=m; ++i){
            if(finish[i]==0) {
                stop = false;
            };
        }
        if(stop) break;
    }
    cout << timer;
    return 0;
}