[BOJ] 1021번 : 회전하는 큐 (C/C++)

BOJ 링크 :  https://www.acmicpc.net/problem/1021

문제

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

첫번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.

왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.

오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이 때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

예제 input

10 3

1 2 3

output

0

해설

큐에서 데이터가 빠지는 횟수만 출력하면 되기때문에 전체 데이터를 가지고다닐 필요가 없다고 생각했다.

그래서 큐의 front 인덱스값과 rear 인덱스값만 가지고 문제를 풀었다.

1) 원소 뽑아내기 -> front++;

2) 왼쪽으로 한 칸 이동 -> rear = front, front++;

3) 오른쪽으로 한 칸 이동 -> front=rear, rear--;

이와같이 계산하면 위 세가지 행동을 front와 rear의 값만으로 할 수 있다.

위 세가지 행동을 bfs를 이용하여 가장 적은 횟수로 뽑아내고 싶은 원소를 찾는다.

필요한 변수

arr[51] -> 뽑아낼 위치를 담을 배열

del[51] -> 큐에 담긴 데이터 현황. 뽑아내면 값을 0에서 1로 바꾸어준다.

chk[51][51][51] -> chk[a][b][c] 라고 하면   c번째 데이터를 제거하려고 찾을 때 (a, b)를 이미 방문했는지 체크하는 배열

풀이 순서

1. arr배열에 뽑아낼 위치를 차례로 담는다

2. 찾고싶은 위치가 될 때 까지 dfs를 이용하여 왼쪽이나 오른쪽으로 탐색한다.

   2-1. 큐를 생성하고 현재 front와 rear, 횟수(0)를 담는다

   2-2. 큐가 빌 때 까지 반복한다.

          2-2-1. 왼쪽으로 움직였을 때와 오른쪽으로 움직였을 때의 front와 rear, cnt+1을 큐에 담는다.

                   front값과 rear값을 증감할 때 이미 제거된 숫자이면 안되고, 변경된 front와 rear가 이번 회차에 방문하지 않았어야 한다.

   2-3. 큐의 top의 front값이 뽑으려는 위치와 일치하면서 지금까지 발견한 cnt중 가장 작은 값을 리턴한다.

3. 찾고싶은 위치의 원소를 뽑는다

    3.1. front값을 1 증가시킨다.

    3.2. 이미 삭제된 데이터이면 3.1로

    3.3. del배열에서 찾은 원소의 값을 1로 바꾸어 삭제되었다고 표시해준다.

#include<cstdio>
#include<queue>
using namespace std;
int n, m;
int del[51];
int arr[51];
int chk[51][51][51];
int front, rear;
int idx;
int ans;
struct Node { int f, r, cnt; };
 
int func()
{
    queue<Node> q;
    q.push({ front, rear, 0 });
    int ret = 99999999;
    while (q.size())
    {
        Node no = q.front(); q.pop();
        int f = no.f, r = no.r, cnt = no.cnt;
        if (f == arr[idx])
        {
            front = f;
            rear = r;
            if (ret > cnt) ret = cnt;
        }
 
        int ff = f;
        while (1)
        {
            ff++;
            ff %= n;
            if (ff == 0) ff = n;
            if (del[ff] == 0) break;
        }
        if (chk[ff][f][idx] == 0)
        {
            chk[ff][f][idx] = 1;
            q.push({ ff, f, cnt + 1 });
        }
 
 
        int rr = r;
        while (1)
        {
            rr--;
            rr %= n;
            if (rr == 0) rr = n;
            if (del[rr] == 0) break;
        }
        if (chk[r][rr][idx] == 0)
        {
            chk[r][rr][idx] = 1;
            q.push({ r, rr, cnt + 1 });
        }
    }
    return ret;
}
 
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) scanf("%d", &arr[i]);
    front = 1, rear = n;
 
    for (int i = 0; i < m; i++)
    {
        ans += func();
        idx++;
        del[front] = 1;
        if (i == m - 1) break;
        while (1)
        {
            front++;
            front %= n;
            if (front == 0) front = n;
            if (del[front] == 0) break;
        }
    }
 
    printf("%d\n", ans);
}