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

백준의 컨베이어 벨트 위의 로봇(20055) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

컨베이어 벨트를 이용해서 로봇들을 옮기는 과정에서, 최종적으로 몇 번 작업을 수행할 수 있는지 구해야 하는 문제이다.

먼저 주어진 변수들을 어떻게 관리했는지부터 시작해서 각 과정에 대한 내용들 그리고 정답을 도출하는 과정까지 진행해보자.

#1. 컨베이어 벨트 관리

본인은 처음 문제를 해결할 때에는 벨트를 윗줄과 아랫줄로 구분해서 2개의 줄로 만들어서 관리를 해 주었다.

실제 코드에서 선언할 때에는 2차원 배열을 통해서 이를 표현해 주었다.

그리고 벨트가 움직일 때, 로봇들이 움직일때를 모두 하나하나 구현하였더니 정답은 받을 수 있었지만 시간초과를 받게 되었다.

그래서 컨베이어 벨트를 조금은 다른 방법으로 표현해 주었다.

컨베이어 벨트를 1개의 줄로 생각을 하는 것이다. 즉, 2N개의 칸을 가지고 있는 하나의 줄로 만들어 주었다.

실제 코드에서는 1차원 배열로 이를 표현해 주었다.

#2. 로봇 관리

본인은 로봇을 관리할 때에는 2가지를 관리해 주었다.

1. 컨베이어 벨트 위에 있는 로봇

2. 컨베이어 벨트 위에 올라간 순서에 따른 로봇

위의 2가지 정보들을 모두 가지고 있어야 한다.

1). 컨베이어 벨트 위에 있는 로봇에 대한 정보를 알고 있어야 하는 이유

   로봇을 시작점에 올리거나, 혹은 로봇이 움직이거나 하는 상황일 때, 해당 컨베이어 칸에 로봇이 이미 위치하고 있는지

   없는 지에 따라서 결과가 달라지기 때문이다.

   그래서 이를 관리하기 위해서 또 하나의 2N개의 칸을 가지는 배열을 하나 선언해 주었다. (본문 : bool Visit[])

   Visit[a] = true 가 의미하는 값은, "컨베이어 벨트의 a번 칸에는 이미 로봇이 있습니다." 라는 것을 의미한다.

   false라면 그 의미는 반대가 될 것이다.

2) 컨베이어 벨트 위에 올라간 순서에 따른 로봇에 대한 정보를 알고 있어야 하는 이유

   로봇이 컨베이어 벨트에 올라간 순서에 대한 정보 또한 알고 있어야 한다. 왜냐하면, 로봇을 움직일 때에는 "가장 먼저 올라간

   로봇부터" 움직여 주어야 하기 때문이다.

   또한 "먼저 올라간 놈이, 먼저 움직여야 한다." 라는 개념에서 본인은 로봇을 자료구조 Queue를 이용해서 관리해 주었다.

   Queue는 선입선출 구조로, "먼저 들어간 놈이, 먼저 나오게 된다".

   따라서, "Queue를 이용해서 컨베이어 벨트 위에 올라간 순서에 따른 로봇의 정보를 관리" 해 주었다.

   구체적인 방법은 아래에서 알아보도록 하자.

이제 문제에서 핵심적인 컨베이어 벨트와 로봇들을 어떻게 관리할지에 대해서 이야기했으니 구체적인 풀이 과정으로 넘어가보자.

#3. 1단계 : 컨베이어 벨트가 한 칸 회전한다.

벨트가 한 칸 회전하는 과정을 알아보자. 물론, 벨트가 한 칸 움직임에 따라서 컨베이어 벨트 위에 있는 로봇들 또한 당연히 한 칸 같이 움직이게 될 것이다.

그럼, 벨트를 회전시키기 전에 벨트가 회전함으로써 일어나는 가장 큰 변화가 무엇인지에 대해서 한번 생각을 해보자.

N = 3 인 벨트를 위에서 이야기 했듯이, 한 줄의 형태를 가진 벨트로 그려본다면, 벨트는 다음과 같은 형태일 것이다.

.

벨트는 위와 같은 형태일 것이다. 2N번인 6번 칸에서 다시 1번 칸으로 순환하는 형태로 표현이 가능하다.

그리고 초기에 로봇이 올라가는 위치 = 1번, 로봇이 내려가는 위치 = 3번 이 될 것이다.

(로봇이 내려가는 위치는, 위의 컨베이어 벨트를 한 줄이 아닌 2줄로 표현했을 때, N번째 칸이 되므로 3번칸이 됩니다.)

그럼 올라가는 위치와 내려가는 위치를 빨강색 동그라미와 초록색 동그라미로 표현해보겠다.

.

이 때, 벨트가 한 칸 회전하게 되었을 때를 그려보면 다음과 같이 표현될 것이다.

.

한 칸 회전하게 되면 위와 같은 그림으로 컨베이어 벨트의 상황이 바뀌게 될 것이다.

그럼, 컨베이어 벨트가 회전하기 전과 회전한 후, 가장 크게 달라진 것이 뭐가 있는지 한번 찾아보자.

바로, "로봇이 올라가는 위치" 와 "로봇이 내려가는 위치" 가 가장 크게 달라졌다.

회전하기 전에는 로봇이 올라가는 위치 = 1 , 내려가는 위치 = 3 이였지만, 한 칸 회전한 후에 보니,

로봇이 올라가는 위치 = 6 , 내려가는 위치 = 2 로 바뀌게 되었다.

그 이외에 별다른 차이점이 있을까 ?? 없다. 즉 ! 컨베이어 벨트가 한번 회전하게 되면, 로봇이 올라가는 위치와 내려가는 위치만 바뀔 뿐, 그 이외에 큰 차이점이 존재하지 않는다는 것이다.

여기서 우리는, 컨베이어 벨트가 한번 회전할 때, 실제로 배열의 인덱스값을 옮기고 말고 할 필요가 없이, 단순히, 로봇이 올라가는 위치와 내려가는 위치만 변경해 주면 된다는 것을 알 수 있다.

구체적으로 변경되는 값을 보게 되면, 올라가는 위치 = 올라가는 위치 - 1 , 내려가는 위치 = 내려가는 위치 - 1 이 되어진다.

물론, 위에서 계산한 값이 0이 되어버린다면, 이는 2N 번으로 바뀌게 된다.

따라서 본인은, 올라가는 위치와 내려가는 위치를 따로 저장해 주었다.(본문 : int Start, int End)

그리고 벨트가 회전하는 과정에서는 이 올라가는 위치와 내려가는 위치에 대한 값만 변경시켜 주었다.

void Move_Belt()
{
    Start--;
    End--;
    if (Start < 1) Start = 2 * N;
    if (End < 1) End = 2 * N;
}
 

본인이 구현한 1단계 : 컨베이어 벨트가 한 칸 회전한다. 를 구현한 코드이다.

그럼 여기서, "컨베이어 벨트 위에 있는 로봇은 어떻게 바뀌게 될까?" 라는 의문이 든다.

이 부분에 대해서 이야기를 해보자.

#2에서 본인은, 컨베이어 벨트 위에 있는 로봇은 또 다른 배열을 하나 선언해서 표시해 주었다고 이야기했다.

예를 들어서 N = 3이고, 현재 1번칸에 로봇이 하나 있다고 가정해보자. 그럼, Visit[1] = true로 선언이 되어 있을 것이다.

그리고 현재 올라가는 위치 = 1 , 내려가는 위치 = 3 이라고 가정해 보겠다.

이 후, 컨베이어 벨트가 한 칸 회전했다. 그럼 올라가는 위치 = 6 , 내려가는 위치 = 2 가 될 것이다.

그리고 로봇이 하나 올라올 수 있는지 판단해보자. 로봇이 올라가는 위치는 현재 '6'이고, '6'에는 로봇이 없기 때문에

로봇이 올라갈 수 있다.

즉 ! 로봇에 대한 관리를 따로 하지 않아도 되는 것이다. Visit[1] = true라고 되어있다 하더라도, 우리에게 이 '1'번은 더 이상 올라가는 위치가 아니기 때문이다. 따라서, 벨트를 움직이는 과정에서는 올라가는 위치와 내려가는 위치에 대한 변경만 필요할 뿐,

로봇에 대해서는 별도의 관리를 해주지 않아도, 마치 로봇이 같이 움직인 것과 같은 효과를 받을 수 있다.

#4. 2단계 : 로봇이 한 칸 움직인다.

컨베이어 벨트 위에 먼저 올라간 순서로, 로봇들이 한 칸씩 움직여야 하는 부분이다.

본인은 이를 Queue를 이용해서 관리해 주었다고 #2 에서 이야기 했었다.

그럼 Queue에서 먼저 들어간 놈들부터 하나씩 꺼내어서 어떻게 처리할지를 이야기 해보자.

Queue에서 현재 컨베이어 벨트의 'A번'에 위치해 있는 로봇을 가져왔다고 가정해보자.

우리는 이 로봇에 대해서 다음에 대한 정보들을 생각해 주어야 한다.

1. 현재 A번이 내려가야 하는 위치인가 ?

2. 1번이 아니라면, A + 1번 칸으로 움직일 수 있는가 ?

3. 2번에 부합하면, A + 1번 칸이 내려가야 하는 위치인가 ?

위와 같이 3가지 정보들을 생각해 주어야 한다.

1. 현재 A번이 내려가야 하는 위치인가 ?

- 당연히 고려해 주어야 하는 부분이다. 왜 그럴까 ?? 바로 #3에서 진행했던, "컨베이어 벨트가 움직이는 과정" 때문에 그렇다.

  예를 들어서 이전에 내려가는 위치가 A + 1번이었는데, #3에 의해서 내려가는 위치가 A번이 되었다고 가정해보자.

  그렇다면, 이 로봇은 실제로는 #3에서 진행했던, 컨베이어 벨트의 움직임에 의해서 이미 내려갔어야 하는 로봇이다.

  하지만 ? #3에서 그런거 처리해주지 않았다. 따라서, 현재 위치가 내려가야 하는 위치에 있는 로봇이라면,

  그대로 로봇을 없애 버리면 된다.

2. 1번이 아니라면, A + 1번 칸으로 움직일 수 있는가 ?

- 내려가야 하는 칸이 칸이라면, A + 1번 칸으로 움직일 수 있는지 판단해 주어야 한다.

  A + 1번 칸의 내구도와, 로봇이 이미 있는지에 대한 여부를 판단해 주면 된다.

  움직일 수 있다면 로봇을 움직여 주면 된다.

3. 2번에 부합하면, A + 1번 칸이 내려가야 하는 위치인가 ?

- 2번에 부합해서, A번 칸에 있는 로봇을 A + 1번칸으로 움직였다고 가정해보자.

  그런데, A + 1번칸이 내려가야 하는 위치라면 바로 로봇을 내려주어야 한다.

  만약 바로 안내려주면 어떻게 될까 ??

  어차피, 그 다음턴에서 로봇이 움직이는 과정을 반복하게 되면, 우리가 1번에서 고려했던, "현재 A번이 내려가야 하는

  위치인가?" 에서 어차피 내려지게 되지 않을까 ??

  그렇지 않다. 왜냐하면 그전에 있는 #3의 과정, 컨베이어 벨트가 한 칸 움직이는 과정에 의해서, 로봇이 내려지지 않고

  그 다음 칸으로 넘어가 버리는 경우가 발생할 수 있다. 아까도 말했지만, #3의 과정에서는 로봇에 대한 처리를

  따로 해주지 않았다.

  따라서, 로봇이 A + 1번칸으로 움직일 수 있다면, A + 1번 칸이 내려가야 하는 위치인가에 대해서 판단해 주어야 하고,

  내려가야 하는 위치라면 로봇을 바로 내려 주어야 한다.

void Move_Robot()
{
    int Size = Robot.size();
    for (int i = 0; i < Size; i++)
    {
        int Cur = Robot.front();
        Visit[Cur] = false;
        Robot.pop();
        
        if (Cur == End) continue;
 
        int Next = Cur + 1;
        if (Next > 2 * N) Next = 1;
        if (Belt[Next] >= 1 && Visit[Next] == false)
        {
            Belt[Next]--;
            if (Belt[Next] == 0) Cnt++;
            if (Next == End) continue;
            Visit[Next] = true;
            Robot.push(Next);
 
        }
        else
        {
            Visit[Cur] = true;
            Robot.push(Cur);
        }
    }
}

본인이 구현한 로봇을 움직이는 코드이다.

line4)에서 주의해야 할 점은, 반복문을 while(Q.empty() == 0) 으로 설정을 하면 안된다는 것이다.

현재 컨베이어 벨트 위에 있는 로봇들을 순서대로 뽑으면서, 움직일 수 있는 로봇들에 대해서만 다시 Queue에 삽입하는 과정을

반복할 것인데, while(Q.empty()==0) 이라는 반복문을 걸어놓으면, 끝나지 않게 된다.

(사실, 본인이 익숙함에 너무 속아, Queue에 대한 반복문은 while(Q.empty() == 0) 으로 설정하는 것에 익숙해져서 구현할 때,

 끝나지 않는 무한루프를 잠시 경험했습니다.)

line7)을 보게되면, "현재 위치에 로봇이 없다" 라고 먼저 표시를 해 주었다. 어차피 움직일 로봇이기 때문이다.

line10)은 내려가야할 위치일 경우에 대한 판단.

line14)는 움직일 수 있을 때에 대한 내용으로, 움직일 수 있다면 그 칸이 내려가는 칸인지에 대해서 판단을 해주어야 한다.

line23)은 움직일 수 없을 경우에 대한 내용으로, 움직일 수 없다면 그 자리에 다시 로봇을 삽입해 주어야 한다.

#5. 3단계 : 로봇 만들기

로봇을 올릴 수 있다면 하나의 로봇을 컨베이어 벨트에 올려야 하는 과정이다.

우리가 올려야 하는 위치는 ? 바로 "Start"라는 변수를 따로 선언해서 관리해 주고 있다.

즉, 'Start'칸에 로봇이 없고, 그 칸의 내구도가 1이상이라면 로봇을 올려주면 된다.

#6. 정답 도출하기

이제 정답을 한번 도출해보자. 위의 과정에서 과연 내구도가 감소하는 칸은 언제언제가 있을까 ??

바로, #4에서 로봇이 움직일 때와 #5에서 로봇을 만들 때, 내구도가 감소하는 일이 발생하게 된다.

즉, 로봇을 움직이거나 로봇을 만들 때, 해당 칸의 내구도를 확인하고 감소시키는 과정을 진행해 주면 된다.

그리고 이 때, 감소시킨 내구도가 0이라면 내구도가 0인 칸의 갯수를 ++ 시켜주면 된다.

[ 소스코드 ]

#include <iostream>
#include <queue>
 
#define MAX 220
#define endl "\n"
using namespace std;
 
int N, K, Start, End, Cnt, Answer;
int Belt[MAX];
bool Visit[MAX];
queue<int> Robot;
 
void Input()
{
    cin >> N >> K;
    for (int i = 1; i <= 2 * N; i++) cin >> Belt[i];
    
}
 
void Move_Belt()
{
    Start--;
    End--;
    if (Start < 1) Start = 2 * N;
    if (End < 1) End = 2 * N;
}
 
void Move_Robot()
{
    int Size = Robot.size();
    for (int i = 0; i < Size; i++)
    {
        int Cur = Robot.front();
        Visit[Cur] = false;
        Robot.pop();
        
        if (Cur == End) continue;
 
        int Next = Cur + 1;
        if (Next > 2 * N) Next = 1;
        if (Belt[Next] >= 1 && Visit[Next] == false)
        {
            Belt[Next]--;
            if (Belt[Next] == 0) Cnt++;
            if (Next == End) continue;
            Visit[Next] = true;
            Robot.push(Next);
 
        }
        else
        {
            Visit[Cur] = true;
            Robot.push(Cur);
        }
    }
}
 
void Make_Robot()
{
    if (Visit[Start] == false && Belt[Start] >= 1)
    {
        Visit[Start] = true;
        Belt[Start]--;
        Robot.push(Start);
 
        if (Belt[Start] == 0) Cnt++;
    }
}
 
void Solution()
{
    Start = 1;
    End = N;
 
    while (Cnt < K)
    {
        Answer++;
 
        Move_Belt();
        Move_Robot();
        Make_Robot();
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}