[ 삼성 SW역량 평가 3190 ] 뱀 (c++)

[ 관련 지식 ]

1.<Vector Library> https://modoocode.com/223

 

[ 난이도 ]

★★☆

 

[ 문제 링크 ]

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

 

[ 문제 풀이 ]

N x N 맵에 상어를 2 사과를 1 길을 0으로 두었으며 Vector를 뱀의 형상처럼 쌓아 올려 각각의

요소에 Vector.at(0) = 머리 Vector.at(end) = 꼬리로 이어 주었고 각각의 벡터는 pair를 통해

X, Y 좌표의 정보를 담고 있다.

 

1) 움직임 구현 방법

현재 뱀의 위치정보를 dir 변수로 각각 동(1)서(2) 남(3) 북(4)을 갖도록 한다. 현재 dir에 따라 한번 움직일 때

머리의 위치가 바뀐다. 그리고 for문을 이용하여 각각의 몸통이 다음 몸통 부분의 값을 갖도록 하고 맵상에

표시해준다.

 

2) 사과를 먹지 않을 경우

꼬리가 있던 자리를 0으로 바꿔주고 새로운 머리의 위치에 2를 추가시켜주고 이정보를 Map과 Vector상에

저장한다.

 

3) 사과를 먹는 경우

과거에 꼬리가 있던 자리를 2로 추가해주면 된다.

 

코드를 보자

 

[ 소스 코드 ]

// 헤더 파일을 불러옵니다.
#include <iostream>
#include <vector>
using namespace std;
#define Max_size 101
 
// X : 회전하는 시간, C : 꺾는 방향
int X[Max_size];
char C[Max_size];
// N : 맵의 크기, K : 사과의 개수
int N, K;
// Apple_x : 사과의 x위치 저장변수, Apple_y : 사과의 y위치 저장변수
int Apple_x, Apple_y;
// L = 회전 정보의 개수
int L;
// 초기 방향은 오른쪽:1
int dir = 1;
 
// 뱀의 정보를 담을 Vector를 선언함 각각 X좌표와 Y좌표가 들어감
vector<pair<int, int>> Snake;
 
// Map을 초기화 시킴
int Map[Max_size][Max_size] = { 0 };
 
// 머리의 초기위치와 머리의 과거값 꼬리의 과거값을 저장할 변수 선언
int Head_x = 1;
int Head_y = 1;
int Pre_Head_x = 0;
int Pre_Head_y = 0;
int Pre_Tail_x = 0;
int Pre_Tail_y = 0;
 
// 경과된 시간을 나타내는 변수
int Time = 0;
 
// 머리의 정보를 넣어주는 초기화 함수
void initialize()
{
    Snake.push_back(make_pair(Head_x, Head_y));
}
 
// 인풋을 받아옴
void Load_Input()
{
    Map[1][1] = 2; // 초기 위치를 뱀(2)로 표시함
    cin >> N; // 맵의 크기를 불러옴
    cin >> K; // 사과의 개수를 불러옴
 
    //사과의 개수만큼 맵에 사과의 위치를 표시해줌
    for (int i = 0; i < K; ++i)
    {
        cin >> Apple_x >> Apple_y;
        Map[Apple_x][Apple_y] = 1;
    }
 
    // 위치 정보의 개수 L만큼 시간정보X와 방향정보L을 쌓아놈.
    cin >> L;
    for (int i = 0; i < L; ++i)
    {
        cin >> X[i] >> C[i];        
    }
}
 
// 현재 방향을 체크하는 하고 바꿔주는 함수
void Check_Turn()
{
    //한번 움직일때마다 경과한 시간 Time이 시간정보 X와 동일하다면 방향을 바꿈
    for (int i = 0; i < L; ++i)
    {    // 동: 1, 서: 2, 남: 3, 북 :4
        if (X[i] == Time)
        {
            if (C[i] == 'L')
            {
                if (dir == 1)
                {
                    dir = 4;
                    break;
                }
                if (dir == 2)
                {
                    dir = 3;
                    break;
                }
                if (dir == 3)
                {
                    dir = 1; 
                    break;
                }
                if (dir == 4)
                {
                    dir = 2;
                    break;
                }
            }
 
            if (C[i] == 'D')
            {
                if (dir == 1)
                {
                    dir = 3; 
                    break;
                }
                if (dir == 2)
                {
                    dir = 4;
                    break;
                }
                if (dir == 3)
                {
                    dir = 2;
                    break;
                }
                if (dir == 4)
                {
                    dir = 1;
                    break;
                }
            }
        }
        else continue;
    }
}
 
// 이동하는 함수
int Move()
{
    // 꼬리와 머리의 과거값을 불러옴
    Pre_Head_x = Head_x;
    Pre_Head_y = Head_y;
    Pre_Tail_x = Snake.back().first;
    Pre_Tail_y = Snake.back().second;
 
    // 방향에 따라 머리의 위치정보를 바꿔줌
    if (dir == 1) Head_y = Head_y + 1;
    if (dir == 2) Head_y = Head_y - 1;
    if (dir == 3) Head_x = Head_x + 1;
    if (dir == 4) Head_x = Head_x - 1;
    
    // Ex) Size가 5인 뱀은 꼬리(5)는 4의 위치로, 4는 3의 위치로 ....위치를 바꿔줌
    for (int i = Snake.size()-1; i >= 1; --i)
    {
        Snake.at(i).first = Snake.at(i - 1).first;
        Snake.at(i).second = Snake.at(i - 1).second;
    }
 
    // 헤드는 새로운 포지션을 따라간다.
    Snake.front().first = Head_x;
    Snake.front().second = Head_y;
 
    // 바뀐 머리가 꼬리와 충돌할 경우 1을 리턴하며 함수를 종료한다.
    if (Head_x == Pre_Tail_x && Head_y == Pre_Tail_y)
    {
        Time++;
        return 1;
    }
 
    // 헤드가 이동후 0을 만났다면
    if (Map[Head_x][Head_y] == 0)
    {
        // 꼬리가 있던자리는 0으로 헤드가 있는자리를 2로 바꿔준다.
        Map[Pre_Tail_x][Pre_Tail_y] = 0;
        Map[Head_x][Head_y] = 2;
    }
 
    // 헤드가 만약 사과를 만났다면
    if (Map[Head_x][Head_y] == 1)
    {
        // 과거 꼬리가 있던 자리에 꼬리를 추가시켜주고
        Snake.push_back(make_pair(Pre_Tail_x, Pre_Tail_y));
        // 맵에 추가시켜준다.
        Map[Pre_Tail_x][Pre_Tail_y] = 2;
        // 헤드의 새로운 위치도 2로 바꿔준다.
        Map[Head_x][Head_y] = 2;
        
    }
    // 한번 움직일때마다 시간을 추가 시켜 준다.
    Time++;
    return 0;
}
 
 
// 뱀의 머리가 몸통에 닿았을경우 true를 아니면 false를 반환함
bool Contact()
{    
    for (int i = 1; i < Snake.size(); ++i)
    {
        if ( (Snake.at(0).second == Snake.at(i).second) && (Snake.at(0).first == Snake.at(i).first))
        {
            return true;
        }
    }
    return false;
}
 
int main()
{    
    // 초기화와 인풋을 받아옴
    initialize();
    Load_Input();
 
    // 맵을 벗어나지 않으면 계속 반복
    while ( ((1 <= Head_x && Head_x <= N) && (1 <= Head_y && Head_y <= N)))
    {
        // 현재 방향 정보로 방향을 갱신해주고
        Check_Turn();
        // Move에서 머리가 꼬리에 닿으면 게임이 끝난다.
        int end = Move();
        if (Contact() == true || end == 1)
        {
            break;
        }
    }
    // 시간을 출력하고 시스템을 정상 종료 한다.
    cout << Time;
    return 0;
}