[C++] 백준 20055번: 컨베이어 벨트 위의 로봇

🔗 문제

20055번: 컨베이어 벨트 위의 로봇

20055번: 컨베이어 벨트 위의 로봇

 

🖍 풀이

 

문제를 정리해보자.

1. 컨베이어 벨트가 오른쪽으로 움직인다. 당연히 로봇의 위치도 함께 움직인다.
   1. 이때 나가는 위치에 도달하면 로봇을 버린다.
2. 적재한 로봇은 올라온 순서가 있다. 이 순서대로 로봇을 한 칸 더 이동시킨다.
   1. 이동하려는 곳의 내구성이 1 미만이면 이동하지 않는다.
   2. 이동하려는 곳에 로봇이 있으면 이동하지 않는다.
   3. 로봇을 이동한 후 이동하려는 곳의 내구성을 -1 더한다.
   4. 이때 나가는 위치에 도달하면 로봇을 버린다.
3. 올리는 위치에 로봇을 올린다.
   1. 올리는 위치의 내구성이 1 미만이면 올리지 않는다.
   2. 올리는 위치에 로봇이 있으면 올리지 않는다.
   3. 로봇을 올린 후 올리는 위치의 내구성을 -1 더한다.
4. 내구성이 1 미만인 위치가 K개 이상이 될 때까지 반복한다.

 

---

간단하게 하면

while(K > cnt)
{
	벨트 이동	
	로봇 이동
	로봇 적재
}

 

1. 벨트 이동

이렇게 맵을 빙글 빙글 원으로 돌리면 그냥 1차원 배열로 생각해주면 된다.

시계방향으로 한칸씩 이동할 때 마다 올리는 곳과 나가는 곳의 인덱스는 -1 가 더해진다.

 

1 2 3 4 5 6

6 1 2 3 4 5

 

문제에서 필요한 인덱스는 나가는 곳과 이동하는 곳이기 때문에 이 둘만 잘 저장해주면 된다.

이 방법을 사용하면 벨트가 돌아갈 때마다 배열 값을 변경하지 않아도 된다.

 

 

2. 로봇 이동

로봇이 자발적으로 움직인다. 이 때 적재된 순서대로 로봇을 움직여야 한다.

로봇의 위치 변경과 삽입 삭제가 잦기 때문에 vector는 지양했고,  list로 풀다가 망쳤는데 (ㅋㅋ)

나랑 비슷한 접근법인데 2번 단계 풀이가 좋은 블로그를 찾아 도움을 받았다!

 

링크: https://yabmoons.tistory.com/599

[ 백준 20055 ] 컨베이어 벨트 위의 로봇 (C++)

 

큐를 이용해서 이동가능 유무에 따라 현재, 다음 위치를 집어넣는 방식이었다.

이 방법 나는 왜 생각 못 해냈지? ㅠ 굿

 

3. 로봇 적재

저장해둔 올리는 곳의 위치에 로봇을 올리면 된다.

 

💾  소스

#include <iostream>
#include <queue>

const int MAX = 200 + 1;

int A[MAX] = {0, };
int N, K, LEN;

int solve()
{
    int answer = 0;
    int start=0, end=N-1; // 컨베이어 벨트의 시작 인덱스

    bool visited[MAX] = {false, };
    std::queue<int> q; // 로봇 위치를 순서대로 저장되어 있다.
    
    int cnt = 0;
    while(K > cnt)
    {
        ++answer;
        
        // 컨베이어 벨트가 이동
        start = (--start < 0 ? LEN-1  : start);
        end = (--end < 0 ? LEN-1 : end);
        
        //로봇의 자발적 이동
        int qSize = q.size();
        while(qSize--)
        {
            int pos = q.front();
            visited[pos] = false;
            q.pop();

            if(pos == end) continue;
            
            int next = (pos + 1 >= LEN ? 0 : pos + 1);
            if(visited[next] || A[next] < 1)
            {
                visited[pos] = true;
                q.push(pos);
            }
            else
            {
                if(--A[next] == 0) ++cnt;
                if(next == end) continue;
                
                visited[next] = true;
                q.push(next);
            }
        }
        
        //로봇 올리기
        if(A[start] < 1 || visited[start]) continue;
        if(--A[start] == 0) ++cnt;

        visited[start] = true;
        q.push(start);
    }
    
    return answer;
}

int main()
{
    std::cin >> N >> K;
    LEN = 2*N;
    
    for(int i=0; i<LEN; ++i)
        std::cin >> A[i];
    
    std::cout << solve();
    
    return 0;
}