Algorithm) 백준 3190 뱀 c++

삼성 SW 역량 테스트 기출 문제중 하나입니다.

 

구현 문제인데요

우선 now라는 변수를 사용해 위 0 오른쪽 1 아래 2 왼쪽 3 이렇게 숫자로 바라보고 있는 방향을 구분했습니다. 처음에는 오른쪽을 보고있으니 초기값은 1입니다 now값에 따라 (y,x)를 변화시키죠

 

s는 뱀의 현재 위치를 가지고 있는 vector입니다 s[0]은 꼬리 s[s.size()-1]은 머리부분입니다.

(1,1)부터 시작해서 머리가 앞으로 전진해서 사과가 있으면 길이가 늘어나고 없으면 유지됩니다.

 

이때 전체가 다같이 움직이는게 아니라 몸 길이를 늘려 머리를 다음칸에 위치시켰다가 사과가 아니면 다시 줄이는게 포인트!! 자기 몸에 닿아 game over되는 경우에 중요합니다 

 

#include <iostream>
#include <vector>

using namespace std;
int n,k;
int board[101][101];
vector<pair<int,int>> s;
char dir = 'D';
int now = 1;
int cnt=0;
vector<pair<int,char>> v;
int main() {
    cin>>n>>k;
    int y,x;
    for(int i=0; i<k; i++) {
        cin >> y >> x;
        board[y][x] = 1;
    }
    int l;
    cin>>l;
    int t;
    char d;
    for(int i=0; i<l; i++) {
        cin>> t>> d;
        v.push_back(make_pair(t, d));
    }
    int time =0;
    s.push_back(make_pair(1,1));
    board[1][1] = 2;
    bool turn = false;
    while(1) {

        // 머리 움직임
        pair<int,int> head = s[s.size()-1];
        time++;
        if(turn) {
            if(dir == 'D') {
                now = (now + 1) % 4;
            }
            else if(dir == 'L') {
                now = now - 1;
                if(now == -1) {
                    now = 3;
                }
            }
            turn = false;
        }
        if(now == 0) {
            head.first -= 1;
        }
        else if(now == 1) {
            head.second += 1;
        }
        else if (now == 2) {
            head.first += 1;
        }
        else if (now == 3) {
            head.second -= 1;
        }

        // 끝나는 조건
        if(head.first > n || head.second > n|| head.first <=0 || head.second <= 0 || board[head.first][head.second] == 2) {
            break;
        }

        if(board[head.first][head.second] == 1) { // 있으면 push만
            s.push_back(make_pair(head.first, head.second));
            board[head.first][head.second] = 2;
        } else { // 사과 없는경우 움직임 따라감
            board[s[0].first][s[0].second] = 0; //꼬리칸 치워줌
            for(int i=0; i<s.size()-1; i++) {
                s[i] = s[i+1];
            }
            board[head.first][head.second] = 2;
            s[s.size()-1] = head;
        }
        if(v.size()-1 >= cnt) {
            if(v[cnt].first == time) {
                dir = v[cnt++].second;
                turn = true;
            }
        }
    }
    cout<<time;
}