[백준 20055] 컨베이어 벨트 위의 로봇

www.acmicpc.net/problem/20055

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

으어..계속 틀린 문제

 

로직을 정리하면

1. 컨베이어 벨트가 움직임

2. 다음 칸에 로봇이 없고 내구성이 1이상이라면 로봇도 이동

3. 로봇을 추가

4. 내구성이 0인 곳이 k개 이상이면 stop

 

이다.

3에서 로봇을 추가할 수 있는 곳은 '올라가는 위치'이고 '내려가는 위치'에선 항상 로봇을 빼야한다.

 

 

따라서 로봇이 있는 지 확인하는 배열과 컨베이어 벨트의 내구성을 체크하는 두 배열을 선언한다.

벨트가 움직이거나 로봇이 움직일 때 배열 값이 움직이기 보단 start와 end 포인트만 움직이려고 한다.

 

 

1. 컨베이어 벨트 움직임

start와 end의 위치를 기준으로 봤을 때 컨베이어 벨트가 움직인다면

start -=1, end-=1 이라고 볼 수있다.

 

2. 로봇의 이동

컨베이어 위에 올라와 있는 로봇은 큐에 담아서 관리한다. 이 때 주의할 점은 !q.empty()가 아니라는 점

현재 큐에 있는 모든 로봇에 대해 이동 가능 여부를 판단한다.

 

현재 위치가 '내려가는 위치'라면 로봇을 내리기만 하고 더 이상 확인하지 않는다.

 

현재 위치가 '내려가는 위치'가 아니라면 다음 위치 cur +1에 대해 이동가능 여부를 판단한다.

이동 가능 여부는 1. 다음칸에 로봇이 있는지? 2. 내구성이 1이상인지?이다.

 

이동가능하다면

큐에 다음 위치를 집어 넣고 로봇의 방문 여부를 체크하고 내구성을 1 줄인다.

이동가능하지 않다면

원 상태로 둔다.

 

이 때 내구성이 줄어서 0이 되었다면 zcnt를 체크한다.

 

3. 로봇 추가

'올라가는 지점'에 1. 로봇이 없고 2. 내구성이 1이상이라면 로봇을 올린다.

역시 로봇이 올라갔으므로 큐에 '올라가는 지점'을 푸쉬하고 방문 여부 체크, 내구성을 1 줄인다.

내구성이 0이 되었다면 zcnt++

 

 

그래서 아래와 같은 코드가 나온다.

#include <stdio.h>
#include <queue>

using namespace std;

bool visit[200];
int belt[200];

int n, k;
int zcnt;
queue<int> q;

void conveyorMove(int *start, int *end)
{
  (*start)--;
  (*end)--;

  if (*start < 0)
  {
    *start = 2 * n - 1;
  }

  if (*end < 0)
  {
    *end = 2 * n - 1;
  }
}

void robotMove(int end)
{
  int sze = q.size();
  for (int i = 0; i < sze; i++)
  {

    int cur = q.front();
    visit[cur] = false;
    q.pop();

    if (cur == end)
      continue;

    int next = (cur + 1) % (2 * n);

    // 칸의 내구도가 1이상이고 로봇이 없음
    if (!visit[next] && belt[next] >= 1)
    {
      belt[next]--;
      //칸의 내구도가 0임
      if (belt[next] == 0)
      {
        zcnt++;
      }
      if (next == end)
        continue;
      //로봇을 올려놓는다.
      visit[next] = true;
      q.push(next);
    }
    else
    {
      visit[cur] = true;
      q.push(cur);
    }
  }
}

void pushRobot(int start)
{
  if (!visit[start] && belt[start] > 0)
  {
    belt[start]--;
    visit[start] = true;
    q.push(start);

    if (belt[start] == 0)
    {
      zcnt++;
    }
  }
}

int main(void)
{
  scanf("%d%d", &n, &k);
  int start = 0, end = n - 1;

  for (int i = 0; i < 2 * n; i++)
  {
    scanf("%d", &belt[i]);
  }
  int idx = 1;
  while (1)
  {
    conveyorMove(&start, &end);
    robotMove(end);
    pushRobot(start);
    if (zcnt >= k)
    {
      break;
    }
    idx++;
  }

  printf("%d\n", idx);
  return 0;
}