[3190] 뱀

구분

• 덱 / 큐
• 구현
• 시뮬레이션
• 자료구조

 

문제

 

https://www.acmicpc.net/problem/3190

3190번: 뱀

 

 

풀이

일단 신경써야 할 부분은 

• 뱀의 이동
• 방향 전환

 

일단 뱀이 이동할 판을 2차원 배열로 구성한다.

• 사과 (2)
• 벽 (1)
• 자신의 몸(1)
• 나머지부분(0)

과 같이 구성하는데, 벽과 자신의 몸은 닿으면 죽는 것이 동일하므로, 같은 변수로 넣어준다.

 

뱀의 이동

덱을 이용하여, 머리의 이동은 다음칸을 push_front, 꼬리의 이동은 꼬리칸을 pop_back으로 구현한다.

(2차원 배열 좌표이므로 int,int pair를 저장해야한다.)

머리의 이동시 

시간++ 

• 사과 존재 
  • 꼬리를 pop하지 x
  • 맵에 있던 사과 제거
• 사과 존재 x
  • 꼬리 pop

*주의할 점은 이동시 방향전환이 일어나는지 입력받은 (초, 방향전환하는곳) 을 저장해두고 확인해야한다.

큐에 저장해두고, 꺼내보면서 지난 시간과 동일하면 방향을 전환해준다.

 

방향전환

현재 머리 방향 / 입력으로 들어온 값	L	D
TOP↑	←	→
DOWN↓	→	←
LEFT←	↓	↑
RIGHT→	↑	↓

방향 전환은 몇초, 어느방향으로 방향전환이 일어나는지 큐에 저장된 값을 보고

해당 초 마다 실행해주면되는데,

현재 머리방향과, 입력으로 들어온 머리 방향에 따라 방향이 다음과 같이 달라진다.

 

코드

//
// 뱀
//

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


using namespace std;
typedef pair<int, int> ii;
typedef pair<int, char> ic;


const int SIZE = 100;
const int TOP = 0;
const int BOT = 1;
const int LEFT = 2;
const int RIGHT = 3;


int board[SIZE + 2][SIZE + 2] = {0};
deque<ii> snake;
queue<ic> direction;

void initBoard(int n) {

    for (int i = 0; i < n + 2; i++) {
        for (int j = 0; j < n + 2; j++) {
            if (i == 0 || i == n + 1 || j == 0 || j == n + 1)
                board[i][j] = 1;
        }
    }

}

//지금 향하는 방향과, 틀 방향을 입력하면, 앞으로 향할 방향을 리턴하는 함수
int changeDir(int now, char dir) {

    switch (now) {
        case TOP:
            if (dir == 'L') return LEFT;
            else if (dir == 'D') return RIGHT;
            break;
        case BOT:
            if (dir == 'L') return RIGHT;
            else if (dir == 'D') return LEFT;
            break;
        case LEFT:
            if (dir == 'L') return BOT;
            else if (dir == 'D') return TOP;
            break;
        case RIGHT:
            if (dir == 'L') return TOP;
            else if (dir == 'D') return BOT;
            break;
        default:
            break;
    }
}


void move(int x, int y) {


    ii tmp;

    // 이동했는데 사과가 있는지 확인
    if (board[x][y] == 2) {
        board[x][y] = 0;// 있음 -> 사과만 제거 (꼬리 움직이지 x)
    } else {
        tmp = snake.back();
        board[tmp.first][tmp.second] = 0;
        snake.pop_back(); // 사과 없음 -> 꼬리 제거 tail pop
    }

    //머리 이동하기 push front
    snake.push_front({x, y});
    board[x][y] = 1; //이동한 부분 1로 변경 


}


int main() {

    int n, k;

    cin >> n >> k;

    //경계 초기화
    initBoard(n);
    //뱀 시작위치
    snake.push_front({1, 1});
    board[1][1] = 1;

    // 사과 배치
    int i, j, l;
    while (k--) {
        cin >> i >> j;
        board[i][j] = 2;//사과
    }

    cin >> l;

    int a;
    char d;
    while (l--) {
        cin >> a >> d;
        direction.push({a, d});
    }

    int sec = 0;
    int cur_dir = RIGHT;//최초 머리의 방향 (오른쪽) 
    ii top;

    int x, y;
    while (true) {
        // 이동
        top = snake.front();//현재 머리의 위치 
        sec++;

        //머리의 방향에 따라 어느방향으로 이동할지 결정해줌 
        if (cur_dir == TOP) {
            x = top.first - 1;
            y = top.second;
        } else if (cur_dir == BOT) {
            x = top.first + 1;
            y = top.second;
        } else if (cur_dir == RIGHT) {
            x = top.first;
            y = top.second + 1;
        } else if (cur_dir == LEFT) {
            x = top.first;
            y = top.second - 1;
        }


        //벽과 부딪힘 or 본인 몸과 부딪힘 -> 종료 
        if (board[x][y] == 1) break;

        //이동 
        move(x, y);

        //x초가 끝난 뒤

        //방향 전환 여부 확인
        if (sec == direction.front().first) {
            //방향을 전환
            cur_dir = changeDir(cur_dir, direction.front().second);
            //pop
            direction.pop();
        }


    }

    cout << sec;


}

 

뻘짓

방향 전환 문제는 국룰이 있다고 한다. 

https://iagreebut.tistory.com/236

[C++] 방향,이동 관련 문제

방향전환을 다음과 같이 적용하면 이렇게 간단하게 구현할 수 있다. 

 

 

코드

//
// 뱀
//

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


using namespace std;
typedef pair<int, int> ii;
typedef pair<int, char> ic;


const int SIZE = 100;
ii dir[4] = {{0,  1},  //우
             {-1, 0},  //상
             {0,  -1}, //좌
             {1,  0}}; //하



int board[SIZE + 2][SIZE + 2] = {0};
deque<ii> snake;
queue<ic> direction;

//바운더리에 1추가
void initBoard(int n) {

    for (int i = 0; i < n + 2; i++) {
        for (int j = 0; j < n + 2; j++) {
            if (i == 0 || i == n + 1 || j == 0 || j == n + 1)
                board[i][j] = 1;
        }
    }

}


void move(int x, int y) {


    ii tmp;

    // 이동했는데 사과가 있는지 확인
    if (board[x][y] == 2) {
        board[x][y] = 0;// 있음 -> 사과만 제거 (꼬리 움직이지 x)
    } else {
        tmp = snake.back();
        board[tmp.first][tmp.second] = 0;
        snake.pop_back(); // 사과 없음 -> 꼬리 제거 tail pop
    }

    //머리 이동하기 push front
    snake.push_front({x, y});
    board[x][y] = 1; //이동한 부분 1로 변경


}


int main() {

    int n, k;

    cin >> n >> k;

    //경계 초기화
    initBoard(n);
    //뱀 시작위치
    snake.push_front({1, 1});
    board[1][1] = 1;

    // 사과 배치
    int i, j, l;
    while (k--) {
        cin >> i >> j;
        board[i][j] = 2;//사과
    }

    cin >> l;

    int a;
    char d;
    while (l--) {
        cin >> a >> d;
        direction.push({a, d});
    }

    int sec = 0;
    int cur_dir = 0;//최초 머리의 방향 (오른쪽)
    ii top;

    int x, y;//다음에 머리가 이동할 위치 계산 
    while (true) {
        // 시간 지남 
        sec++;
        
        
        top = snake.front();//현재 머리의 위치
	//방향을 고려한 위치 이동 
        x = top.first + dir[cur_dir].first;
        y = top.second + dir[cur_dir].second;


        //벽과 부딪힘 or 본인 몸과 부딪힘 -> 종료
        if (board[x][y] == 1) break;

        //이동
        move(x, y);

        //x초가 끝난 뒤

        //방향 전환 여부 확인
        if (sec == direction.front().first) {
            //방향을 전환 -> 이렇게 간단하게 구현할 수 있음!
            if (direction.front().second == 'L')
                cur_dir = (cur_dir + 1) % 4;
            else
                cur_dir = (cur_dir + 3) % 4;
            //pop
            direction.pop();
        }


    }

    cout << sec;

}