FIFO 문맥에서 동작하기 위해 설계된 컨테이너 어뎁터

멤버함수

생성

#include <iostream>
#include <deque>
#include <list>
#include <queue>

using namespace std;

int main(void){
    deque<int> d(3, 100);
    list<int> l(2, 50);

    queue<int> q1;
    queue<int> q2(d);
    queue<int, list<int>> q3;
    queue<int, list<int>> q4(l);
}

멤버함수

• empty()
• size()
• front()
• back()
• push()
• pop()
• emplace() * C++11
• swap() * C++11

#include <iostream>
#include <queue>

using namespace std;

int main(void){
    queue<int> q;

    for(int i = 1; i < 10; ++i)
        q.push(i);
    cout << q.back() << '\n';
    // 9
    cout << q.size() << '\n';
    // 9

    while(!q.empty()){
        cout << q.front() << ' ';
        q.pop();
    }
    cout << '\n';
    // 1 2 3 4 5 6 7 8 9
}

문제 링크

풀이 )

  배열에 있는 수를 앞 또는 뒤에서 뺄 수 있도록 하기 위해 deque에 넣었다.

  처음 방향 dir을 true로 설정하고, 함수 R가 올 때마다 dir을 바꿔준다.

  dir에 따라 함수 D가 올 때 true인 경우 앞에서 빼주고 (pop_front()), false인 경우 뒤에서 빼준다. (pop_back())

  이 때, 현재 deque가 비어있는데 D가 나오는 경우 error를 출력하면서 다음 케이스를 실행한다.

  함수를 수행한 결과 deque가 비어있는 경우 "[]"만 출력하고 다음 케이스를 실행하고,

  비어있지 않은 경우 dir에 따라 앞, 뒤에서부터 출력한다.

#include <iostream>
#include <string>
#include <deque>

using namespace std;

int main(void){
    int t;
    cin >> t;
    while(t--){
        string func, s;
        int n;
        cin >> func;
        cin >> n;
        cin >> s;

        deque<int> dq;
        int len = s.length();
        int tmp = 0;
        for(int i = 1; i < len; ++i){
            if(s[1] == ']')
                break;
            if(s[i] == ',' || s[i] == ']'){
                dq.push_back(tmp);
                tmp = 0;
            }
            else
                tmp = tmp*10+s[i]-'0';
        }

        bool dir = true;
        int func_len = func.length();
        bool flag = 0;
        for(int i = 0; i < func_len; ++i){
            if(func[i] == 'R')
                dir = !dir;
            else{
                n--;
                if(dq.empty()){
                    cout << "error" << endl;
                    flag = true;
                    break;
                }
                if(dir)
                    dq.pop_front();
                else
                    dq.pop_back();
            }
        }
        if(flag)
            continue;

        if(n == 0){
            cout << "[]" << endl;
            continue;
        }
        if(dir){
            for(int i = 0; i < n; ++i){
                if(i == 0)
                    cout << '[';
                cout << dq.front();
                dq.pop_front();
                if(i == n-1)
                    cout << ']' << endl;
                else
                    cout << ',';
            }
        }
        else{
            for(int i = 0; i < n; ++i){
                if(i == 0)
                    cout << '[';
                cout << dq.back();
                dq.pop_back();
                if(i == n-1)
                    cout << ']' << endl;
                else
                    cout << ',';
            }
        }
    }
}

주의 )

  각 경우에 대해서 조건을 간단하게 나타낼 수 있다.  ex ) 5를 지나가는 경우 cur+prev == 10

  이 때 4를 지나가는 경우 cur+prev == 8로 나타내는 경우 (2, 6)과 같은 예외가 있기 때문에 주의해야한다.

문제 링크

풀이 ) BFS

  큐에 처음 층을 넣고 큐에서 큐에서 뺄 때 뺀 층에서 갈 수 있는 층을 큐에 넣는다.

  이때 목표층에 도착하는 경우 중첩 반복문에서 빠져나오기 위해 바깥쪽 while문에서도 조건에 따른 break를 추가한다.

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

int main(void){
  int n, k, ans = 0, used[100001] = {0, };
  queue<int> q;

  scanf("%d%d", &n, &k);
  q.push(n);
  q.push(-1);
  used[n]++;

  while(1){
    int tmp = q.front();
    while(tmp != -1){
      if(tmp == k)
        break;
      q.pop();
      if(tmp>0 && !used[tmp-1]){
        used[tmp-1]++;
        q.push(tmp-1);
      }
      if(tmp<99999 && !used[tmp+1]){
        used[tmp+1];
        q.push(tmp+1);
      }
      if(tmp<=50000 && !used[tmp*2]){
        used[tmp*2];
        q.push(tmp*2);
      }
      tmp = q.front();
    }
    if(tmp == k)
      break;
    q.pop();
    ans++;
    q.push(-1);
  }
  printf("%d\n", ans);
}

주의점 )

  사용여부를 확인하기 전에 해당 인덱스(층)에 방문할 수 있는지, 즉 해당 층이 범위 내에 있는지 확인해야 런타임 에러를 방지할 수 있다.

문제 링크

풀이 ) BFS

  버튼을 누르는 횟수를 표시하기 위해 pair를 사용할 수도 있지만 개인적으로 구분자로 사용하는 것이 편해서 구분자 '0'을 사용해서 구현했다.

  현재 있는 층과 구분자 0을 큐에 넣고 시작을 한다.

  반복문 안에서는 큐의 가장 앞 원소를 확인해서 먼저 도착했는지 확인한다.

  이후 구분자인지 확인하고 구분자 뒤에 원소가 없으면 즉 다음에 방문할 층이 없다면 반복문을 종료시키고 엘리베이터를 이용할 수 없기 때문에 ans = -1; break;를 해준다.

  원소가 있다면 아직 방문할 층이 남아있으므로 버튼을 누르는 횟수를 증가시키고, 큐에 구분자를 넣어준다.

  현재층에서 위로 올라갈 수 있으면 (n+u <= f) 다음에 방문할 층을 큐에 넣어준다. 방문 여부를 확인하지 않으면 중복이 발생할 수 있기 때문에 방문 여부도 확인하고, 방문 시 방문 여부를 고친다.

  아래로 갈 수 있으면 (n-d>0) 다음에 방문할 층의 방문 여부를 확인하고 큐에 넣어준다.

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

int f, s, g, u, d, ans;
int visited[1000001];
queue<int> q;
int bfs();

int main(void)
{
  scanf("%d%d%d%d%d", &f, &s, &g, &u, &d);

  visited[s] = 1;
  q.push(s);
  q.push(0);

  while(1){
    int n = q.front();

    if(n == g)
      break;
    if(n == 0){
      q.pop();
      if(q.empty()){
        ans = -1;
        break;
      }
      q.push(0);
      ans++;
      continue;
    }
    q.pop();

    if(n+u <= f && !visited[n+u]){
      visited[n+u] = 1;
      q.push(n+u);
    }
    if(n-d > 0 && !visited[n-d]){
      visited[n-d] = 1;
      q.push(n-d);
    }
  }

  if(ans != -1)
    printf("%d\n", ans);
  else
    printf("use the stairs\n");
  return 0;
}

문제 링크

풀이 )

  개인적인 편의상 이차원배열에서 좌표를 [y][x]로 했다.

  먼저 뱀의 몸이 지나고 있는 자리 board를 배열로 나타내고, 사과 apple의 위치를 나타내기 위한 배열을 따로 만들었다.

  그리고 뱀의 몸을 나타내기 위한 큐 snake와 방향 회전 turn을 만들었다.

  먼저 현재 좌표(curY, curX)가 보드 안에 있는지(벽에 부딪힌지 여부) 확인한 후, 몸에 부딪혔는지 확인하여 부딪혔다면 반복문을 종료하고 결과를 출력한다.

  현재 좌표에 뱀의 머리가 있으므로 뱀에 넣어주고 board의 현재 위치를 1로 만들어준다. 그리고 현재 위치에 사과가 없다면(!apple[curY][curX]) 뱀의 꼬리, 즉 가장 먼저 들어간 원소이므로 front()에 있는 board를 0으로 만들어준다.

  사과가 있다면 사과를 먹었으므로 다시 apple[curY][curX]를 0으로 만들어준다.

  다음 회전을 기다리기 위해 회전할 초를 저장하는 next를 만들었다.

  next가 비어있는 경우 turn 큐에서 pop을 해서 몇초인지 next에 넣어주고, 어떤 방향인지 next_dir에 넣어준다.

  이후 회전하는 시간이 되면(ans == next) 방향에 맞게 회전해준다.

  dx, dy를 각각 시계방향으로 만들었기 때문에 오른쪽이면 (dir+1)%4, 왼쪽이면 (dir-1+4)%4로 해준다. 이 때 왼쪽의 경우 +4를 해주어 dir이 음이 되는 것을 방지한다.

  이후 현재의 좌표를 이동시키고 다음 반복문을 진행한다.

#include <cstdio>
#include <queue>	// queue
#include <utility>	// pair
using namespace std;

int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};

int main(void)
{
  int n, k, l, board[101][101] = {0, }, apple[101][101] = {0, };
  char c[101] = "";
  queue<pair<int, int>> snake;
  queue<pair<int, char>> turn;

  scanf("%d%d", &n, &k);
  for(int i = 0; i < k; ++i){
    int x, y;
    scanf("%d%d", &y, &x);
    apple[y][x]++;
  }
  scanf("%d", &l);
  for(int i = 0; i < l; ++i){
    int x;
    char dir;
    scanf("%d %c", &x, &dir);
    turn.push(make_pair(x, dir));
  }

  int ans = 0, curX = 1, curY = 1, dir = 1, next = 0;
  char next_dir;

  while(1){
    // 부딪힌지 여부
    if(curX < 1 || curX > n || curY < 1 || curY > n)
      break;
    if(board[curY][curX])
      break;

    snake.push(make_pair(curY, curX));
    board[curY][curX] = 1;
    // 사과가 없을 때
    if(!apple[curY][curX] && ans){
      int tmpX, tmpY;
      tmpX = snake.front().second;
      tmpY = snake.front().first;
      snake.pop();
      board[tmpY][tmpX] = 0;
    }
    // 사과가 있을 때
    else
      apple[curY][curX] = 0;

    // 다음 회전
    if(next == 0){
      next = turn.front().first;
      next_dir = turn.front().second;
      turn.pop();
    }
    if(ans == next){
      next = 0;
      if(next_dir == 'L')
        dir = (dir+3)%4;
      else
        dir = (dir+1)%4;
    }
    ans++;
    curX += dx[dir];
    curY += dy[dir];
  }
  printf("%d\n", ans);
  return 0;
}

주의점 )

  - 좌표 범위

  - 회전

문제 링크

풀이 ) BFS

  부모 자식 관계를 배열로 나타냈다. 이 때 행, 열의 구분은 중요하지 않다.

  입력으로 들어온 촌 수를 구하고자 하는 사람 중 한명을 큐에 먼저 넣는다. 촌수를 구하기 위해 촌수를 구분하기 위해 구분자 역할을 하는 0을 넣어주었다.

  입력으로 들어온 두 사람의 촌 수가 존재한다면 그 방향성은 중요하지 않기 때문에 큐에 넣고 빼는 동작을 하는 과정에서는 답이 증가하기만 한다.

  과정을 반복하는 중 큐가 비었을 때, 즉 딜리미터인 0이 연속으로 있는 경우는 촌수관계가 없기 때문에 -1을 출력한다.

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

int n, in[2], m, child, parent, rel[101][101], visited[101], ans;
queue<int> q;

void bfs(int curr);

int main(void)
{
  scanf("%d", &n);
  scanf("%d%d", in, in+1);
  scanf("%d", &m);
  for(int i = 0; i < m; ++i){
    scanf("%d%d", &child, &parent);
    rel[child][parent]++;
    rel[parent][child]++;
  }
  bfs(in[0]);
  printf("%d\n", ans);
}

void bfs(int curr)
{
  visited[curr]++;
  q.push(curr);
  q.push(0);
  while(1){
    int next = q.front();
    if(next == in[1])
      return;
    if(next == 0){
      q.pop();
      if(q.front() == 0){
        ans = -1;
        return;
      }
      q.push(0);
      ans++;
      continue;
    }
    q.pop();
    for(int i = 1; i <= n; ++i)
      if(rel[next][i] && !visited[i]){
        visited[i]++;
        q.push(i);
      }
  }
}