[BOJ] 3190번 뱀 문제풀이 (C++)

2017.10.13에 쓰여진 글 입니다.

---

 

문제 링크

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

3190번: 뱀

 

풀이방법

뱀 문제는 일단 풀이방법이 2가지가 있음.

1. 리스트 이용

2. 덱 이용

예전에는 리스트를 이용해서 풀었는데 이번에는 덱을 이용해서 풀어봄.

덱이용해서 푼 버전으로 설명하면

뱀의머리좌표를 움직이는 것임.

머리가 움직이면 꼬리는알아서 따라옴

(뱀의 꼬리)4 3 2 1(뱀의 머리)

이렇게 진행중이라고 해보면

deque를 이용하면 양끝에서 push pop이 가능하기때문에 

1. 아무것도 없는곳일 경우에는 다음좌표를 push_front()해주고 꼬리좌표를 pop_back()해줌

 4 3 2 1  (그대로이면서 좌표만 한칸이동)

2. 사과를 먹으면 다음좌표만 push_front()해줌

4 3 2 1 0 (추가해줌)

3. 방향전환 다음좌표를 push_front()해주고 꼬리좌표를 pop_back()해줌

  4 3 2

       1

 

이런식으로 진행함.

그리고 명령을 다쓰고 나면 그냥 죽을때까지 현재진행방향으로 진행해줌. 

그냥 시키는대로 하면 되는 문제임

 

소스코드

소스코드1 (List 이용)

#include <iostream>
#include <queue>    //queue 위한 헤더
#include <utility>    //pair 위한 헤더
#include <list>        //list 위한 헤더
 
using namespace std;
 
enum maps { BLANK = 0, SNAKE = 1, APPLE = 2 };
enum direction { EAST = 0, SOUTH = 1, WEST = 2, NORTH = 3 };
 
int map[101][101];        //맵생성
queue <pair<int, char> > q;      //방향변환정보저장
int Answer;      //정답시간
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,-1,1 };
list <pair<int, int> > bam;    //뱀 리스트선언!
list <pair<int, int> >::iterator itor;    //리스트접근 반복자
 
void Init_map()      //맵초기화
{
    for (int i = 0; i <= 100; i++)
        for (int j = 0; j <= 100; j++)
            map[i][j] = BLANK;
}
 
void Check(int cur_x, int cur_y, int cur_dir, int size)
{
    if (!q.empty() && Answer == q.front().first) { //q가 비어있지 않고 방향전환할 초가 되었다면
        char turn_dir = q.front().second;
        if (turn_dir == 'L')
            cur_dir = (cur_dir + 3) % 4;    //왼쪽방향으로 회전
        else
            cur_dir = (cur_dir + 1) % 4;    //오른쪽방향으로 회전
        q.pop();    //방향변환정보 첫번째로넣은거 빼줌 
    }
    Answer++;//초증가
    int new_x, new_y;    //다음에갈위치
    switch (cur_dir) {   // 동0 남1 서2 북3
    case(EAST):   //현재 뱀의 진행방향 동
        new_x = cur_x;
        new_y = cur_y + 1;   //동쪽으로 한칸이동
        break;
    case(SOUTH):   //현재 뱀의 진행방향 남
        new_x = cur_x + 1;
        new_y = cur_y;   //남쪽으로 한칸이동
        break;
    case(WEST):
        new_x = cur_x;
        new_y = cur_y - 1;
        break;
    case(NORTH):
        new_x = cur_x - 1;
        new_y = cur_y;
        break;
    }
    for (itor = bam.begin(); itor != bam.end(); itor++)
        if (itor->first == new_x&&itor->second == new_y)    //본인 몸통과 만나면 끝
            return;
    if (new_x > size || new_y > size ||      //새로 갈려고 하는 위치가 뱀이 지도를 벗어나면 끝
        new_x < 1 || new_y < 1) {
        return;
    }
    else {      //끝나지 않으면
        if (map[new_x][new_y] == BLANK) {    //사과없는칸
            bam.push_front(make_pair(new_x, new_y));    //다음좌표머리로 넣어줌
            bam.pop_back();//제일 꼬리부분 삭제
        }
        else {    //사과먹음
            bam.push_front(make_pair(new_x, new_y));
            map[new_x][new_y] = BLANK;    //사과먹었으니 빈칸으로 바꿔준다
        }
        Check(new_x, new_y, cur_dir, size);        //다음좌표 또 체크!
    }
}
 
int main()
{
    Answer = 0;
    int N, K, L;
    int X;
    cin >> N >> K;
    Init_map();//맵초기화
    bam.clear();//뱀 list 초기화
    for (int m = 0; m < K; m++) {   //사과있는좌표에 APPLE을 넣음 
        int i, j;
        cin >> i >> j;
        map[i][j] = APPLE;
    }
    bam.push_front(make_pair(1, 1));    //뱀의 첫번째 머리 위치 리스트에 저장
    cin >> L;
    for (int i = 0; i < L; i++) {   //방향변환정보(좌표) q에 저장
        int x = 0;
        char c = NULL;
        cin >> x >> c;
        q.push(make_pair(x, c));
    }
    Check(1, 1, EAST, N);        //첫번째좌표, 방향, 맵 사이즈 넣어주기
 
    cout << Answer << endl;
 
    return 0;
}

 

소스코드2 (deque 이용)

#include <iostream>
#include <deque>        //덱 위한 헤더
#include <queue>        //큐 위한 헤더
 
using namespace std;
 
enum { BLANK = 0, APPLE = 1, SNAKE = 2 };            //지도에 표시
enum DIR { UP = 0, RIGHT = 1, DOWN = 2, LEFT = 3 };    //방향
 
int N, K, L;
int map[100][100];
queue < pair < int, char > > q;    //명령저장
deque < pair < int, int > > dq;    //좌표저장
int Answer;
bool flag;                    //뱀이 죽었는지 체크
int cur_dir;                //현재방향
int dx[] = { -1,0,1,0 };    //위,오른쪽,아래,왼쪽
int dy[] = { 0,1,0,-1 };
 
void Init_map()
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            map[i][j] = BLANK;
}
 
void solve(int time, char turn)
{
    int start_time = Answer;                    //시작시간을 Answer로
    for (int i = start_time; i < time; i++) {    //시작시간부터 명령시간까지 돌림
        Answer++;                                //현재시간 증가
        int cur_x = dq.front().first;            //뱀의 머리좌표저장
        int cur_y = dq.front().second;
        int last_x = dq.back().first;            //뱀의 꼬리좌표저장
        int last_y = dq.back().second;
        int new_x = cur_x + dx[cur_dir];        //머리가 이동할 방향좌표 저장
        int new_y = cur_y + dy[cur_dir];
        if (0 <= new_x&&new_x < N && 0 <= new_y&&new_y < N) {    //범위안에있으면
            dq.push_front(make_pair(new_x, new_y));                //그 이동할좌표를 뱀의 머리좌표로 해줌(deque에 앞에 push)
            if (map[new_x][new_y] == BLANK) {                    //좌표상에서 그 지점이 빈칸이면
                map[new_x][new_y] = SNAKE;                        //뱀이라고 표시
                map[last_x][last_y] = BLANK;                    //꼬리좌표를 빈칸으로 만들기
                dq.pop_back();                                    //꼬리좌표 deque에서 빼줌
            }
            else if (map[new_x][new_y] == APPLE) {                //사과면
                map[new_x][new_y] = SNAKE;                        //사과라고표시해줌
            }
            else {                //뱀이면
                flag = false;    //게임끝. 뱀죽음
                break;            //해볼필요도 없이 탈출
            }
        }
        else {                //범위벗어나면
            flag = false;    //게임끝
            break;            //탈출 ㄱㄱ
        }
    }
    if (turn == 'D')
        cur_dir = (cur_dir + 1) % 4;        //진행방향의 오른쪽으로
    else if (turn == 'L')
        cur_dir = ((cur_dir - 1) + 4) % 4;    //진행방향의 왼쪽으로
    else
        return;        //그냥 원래방향유지
}
 
int main()
{
    Answer = 0;
    cin >> N >> K;                    //입력받기
    Init_map();                        //맵초기화
    for (int i = 0; i < K; i++) {
        int x, y;
        cin >> x >> y;
        map[x - 1][y - 1] = APPLE;    //지도에 사과표시
    }
    cin >> L;                        //명령
    for (int i = 0; i < L; i++) {    //명령저장
        int X;
        char C;
        cin >> X >> C;
        q.push(make_pair(X, C));    //큐에 저장해놓기
    }
    dq.push_front(make_pair(0, 0));    //뱀 시작점 저장
    map[0][0] = SNAKE;                //뱀 지도에 표시
    cur_dir = RIGHT;                //초기 방향 오른쪽
    flag = true;                    //뱀 살아있으면 true, 죽으면 false
    while (flag) {                    //뱀이 살아있을때 계속 돌림
        int time = 987654321;        //시간 초기화
        char turn = 'X';            //방향 초기화
        if (!q.empty()) {            //명령이 남아있으면
            time = q.front().first;    //명령넣어주고
            turn = q.front().second;
            q.pop();                //큐빼줌
        }
        solve(time, turn);            //solve함수 호출
    }
    cout << Answer << endl;
 
    return 0;
}