백준 3190 - 뱀 (c++)

백준 3190 - 뱀

문제 링크

생각 및 접근

• 어릴 적에 했었던 뱀 게임이다.

• 주어지는 것은

  • n : 보드의 크기
  • k : 사과의 갯수
  • vector<pair<Loc, bool>> apple; : 사과의 좌표
  • l : 뱀의 회전 횟수
  • vector<pair<int, char>> Rotate; : 뱀의 회전 방향 및 시간
    이다.

• 수도 코드는 이렇다.

    int main() {
        // 문제의 입력을 받는다.
  
        while(-1){
            // 뱀의 머리 위치와 방향을 토대로 다음 머리 위치를 찾는다.
            // 방향을 바꿔야 한다면, 방향을 바꿔준다
  
            // 다음 머리 위치에 벽이 있는지 확인한다.
            // 다음 머리 위치에 뱀의 몸통이 있는지 확인한다.
                // 위 두 가지 조건을 만족하면, 더이상 뱀이 앞으로 전진할 수 없다는 의미이므로 break;
  
            // 다음 머리 위치에 사과가 있는지 확인한다.
                // 사과가 있다면, 뱀을 다음 머리를 머리로 인정하고, 기존 머리를 몸통으로 인정한다.
                // 사과가 없다면, 뱀의 다음 머리를 머리로 인정하고, 맨 마지막 꼬리를 잘라낸다.
  
            // 시간을 1 늘려준다.
        }
    }

• queue<pair<Loc, int>> snake;

  • 큐의 front는 뱀의 머리, 큐의 back은 뱀의 꼬리, 그 중간에 있는 요소들은 뱀의 몸통이라고 가정하였음.
  • Loc는 좌표를 구조체로 표현. (아래 코드 참조) in는 뱀 머리 방향을 표현.

문제의 입력을 받는다.

struct Loc{
    int x;
    int y;
    Loc(int a, int b) : x(a), y(b) {};
};

// Loc는 뱀의 머리/몸통/꼬리 위치, int는 뱀 머리 방향
queue<pair<Loc, int>> snake;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);

    cin >> n >> k;
    for(int i = 1; i <= k; i++){
        cin >> x >> y;
        // 사과의 좌표 삽입. 두번째 bool은 이 사과를 먹었는 지 기억하는 변수다.
        apple.push_back(make_pair(Loc(y, x), false));
    }

    cin >> l;
    for(int i = 1; i <= l; i++){
        cin >> x >> c;
        // 방향을 바꿔야 할 때를 기억하는 벡터
        Rotate.push_back(make_pair(x, c));
    }

    snake.push(make_pair(Loc(1, 1), RIGHT));

뱀의 머리 위치와 방향을 토대로 다음 머리 위치를 찾는다. 방향을 바꿔야 한다면, 방향을 바꿔준다

const int UP = 0;
const int RIGHT = 1;
const int DOWN = 2;
const int LEFT = 3;

int TURN(int dir, char to){
    if(to == 'L')       return (dir - 1 == -1) ? 3 : dir - 1;
    else if(to == 'D')  return (dir + 1 == 4) ? 0 : dir + 1;
}

x = snake.front().first.x;
y = snake.front().first.y;
dir = snake.front().second;
snake.pop();

// 다음 뱀의 머리 위치
int xx = x + dx[dir];
int yy = y + dy[dir];
int ddir = dir;

// 시간 때문에 뱀의 머리 방향을 바꿔야 한다면, 바꿔준다.
// Rotate는 시간 순서로 주어지기 때문에, idx를 선언하여 시간을 기억해 놓는다.
if(idx < l && Rotate[idx].first == t){
    ddir = TURN(dir, Rotate[idx].second);
    idx++;
}

다음 머리 위치에 벽이 있는지 확인한다.

if(!(xx >= 1 && xx <= n && yy >= 1 && yy <= n)) break;

다음 머리 위치에 뱀의 몸통이 있는지 확인한다.

• snake를 전부 순회해서 다음 머리 위치가 snake에 있는 Loc와 일치하는 지 확인한다.

  int tmp = snake.size();
  for(int i = 1; i <= tmp; i++){
    int tx = snake.front().first.x;
    int ty = snake.front().first.y;
    int tdir = snake.front().second;
    snake.pop();
  
    if(tx == xx && ty == yy){
        cout << t;
        exit(0);
    }
  
    snake.push(make_pair(Loc(tx, ty), tdir));
  }

위 두 가지 조건을 만족하면, 더이상 뱀이 앞으로 전진할 수 없다는 의미이므로 break;

다음 머리 위치에 사과가 있는지 확인한다. 사과가 있다면, 뱀을 다음 머리를 머리로 인정하고, 기존 머리를 몸통으로 인정한다.

• gotApple은 사과가 있는지 확인하는 변수. 뒤에 if문을 위해서 선언해 놓는다.

bool gotApple = false;
for(int i = 0; i < k; i++){
    // 사과를 먹지 않았고, 다음 머리에 사과가 존재한다면 => 사과를 먹은 것으로 처리해야함!
    if(!apple[i].second && apple[i].first.x == xx &&  apple[i].first.y == yy){
        // 이전 머리를 몸통으로 인정하기
        snake.push(make_pair(Loc(x, y), dir));
        int temp = snake.size();
        // 다음 머리를 머리로 인정하기
        // 여기서 뱀의 머리는 snake의 front와 일맥상통.
        snake.push(make_pair(Loc(xx, yy), ddir));
        if(temp != 0){
            for(int i = 1; i <= temp; i++){
                int tx = snake.front().first.x;
                int ty = snake.front().first.y;
                int tdir = snake.front().second;
                snake.pop();

                snake.push(make_pair(Loc(tx, ty), tdir));
            }
        }
        apple[i].second = true;
        gotApple = true;
        break;
    }
}

사과가 없다면, 뱀의 다음 머리를 머리로 인정하고, 맨 마지막 꼬리를 잘라낸다.

if(!gotApple){
    // 이전 머리를 몸통으로 인정하기
    snake.push(make_pair(Loc(x, y), dir));
    int temp = snake.size();
    // 다음 머리를 머리로 인정하기
    snake.push(make_pair(Loc(xx, yy), ddir));
    for(int i = 1; i <= temp; i++){
        int tx = snake.front().first.x;
        int ty = snake.front().first.y;
        int tdir = snake.front().second;
        snake.pop();

        // 꼬리 잘라내기
        if(i != 1)
            snake.push(make_pair(Loc(tx, ty), tdir));
    }
}

시간을 1 늘려준다.

t++;

코드

#include <bits/stdc++.h>
using namespace std;

const int UP = 0;
const int RIGHT = 1;
const int DOWN = 2;
const int LEFT = 3;
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};

struct Loc{
    int x;
    int y;
    Loc(int a, int b) : x(a), y(b) {};
};

char c;
int n, k, l, x, y, idx, t = 1, dir;
vector<pair<Loc, bool>> apple;
vector<pair<int, char>> Rotate;
queue<pair<Loc, int>> snake;

int TURN(int dir, char to){
    if(to == 'L')       return (dir - 1 == -1) ? 3 : dir - 1;
    else if(to == 'D')  return (dir + 1 == 4) ? 0 : dir + 1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);

    cin >> n >> k;
    for(int i = 1; i <= k; i++){
        cin >> x >> y;
        apple.push_back(make_pair(Loc(y, x), false));
    }

    cin >> l;
    for(int i = 1; i <= l; i++){
        cin >> x >> c;
        Rotate.push_back(make_pair(x, c));
    }

    snake.push(make_pair(Loc(1, 1), RIGHT));
    while(-1){
        x = snake.front().first.x;
        y = snake.front().first.y;
        dir = snake.front().second;
        snake.pop();

        int xx = x + dx[dir];
        int yy = y + dy[dir];
        int ddir = dir;
        if(idx < l && Rotate[idx].first == t){
            ddir = TURN(dir, Rotate[idx].second);
            idx++;
        }

        if(!(xx >= 1 && xx <= n && yy >= 1 && yy <= n)) break;
        int tmp = snake.size();
        for(int i = 1; i <= tmp; i++){
            int tx = snake.front().first.x;
            int ty = snake.front().first.y;
            int tdir = snake.front().second;
            snake.pop();

            if(tx == xx && ty == yy){
                cout << t;
                exit(0);
            }

            snake.push(make_pair(Loc(tx, ty), tdir));
        }

        bool gotApple = false;
        for(int i = 0; i < k; i++){
            if(!apple[i].second && apple[i].first.x == xx &&  apple[i].first.y == yy){
                snake.push(make_pair(Loc(x, y), dir));
                int temp = snake.size();
                snake.push(make_pair(Loc(xx, yy), ddir));
                if(temp != 0){
                    for(int i = 1; i <= temp; i++){
                        int tx = snake.front().first.x;
                        int ty = snake.front().first.y;
                        int tdir = snake.front().second;
                        snake.pop();

                        snake.push(make_pair(Loc(tx, ty), tdir));
                    }
                }
                apple[i].second = true;
                gotApple = true;
                break;
            }
        }
        if(!gotApple){
            snake.push(make_pair(Loc(x, y), dir));
            int temp = snake.size();
            snake.push(make_pair(Loc(xx, yy), ddir));
            for(int i = 1; i <= temp; i++){
                int tx = snake.front().first.x;
                int ty = snake.front().first.y;
                int tdir = snake.front().second;
                snake.pop();

                if(i != 1)
                    snake.push(make_pair(Loc(tx, ty), tdir));
            }
        }
        t++;
    }

    cout << t;
}

채점 결과