백준 3190 뱀 C++

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

3190번: 뱀

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ3190.cpp

hwayeon351/BEAKJOON-Algorithms

//
//  main.cpp
//  BJ3190
//
//  Created by 최화연 on 2022/04/08.
//

#include <iostream>
#include <queue>
#include <deque>
using namespace std;

int N, K, L;
int map[101][101] = {0, };
queue<pair<int, char>> cmds;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int sec = 0;

struct Snake {
    deque<pair<int, int>> body = {{1, 1}};
    int dir = 2;
};
Snake snake;

void play_game() {
    map[1][1] = 2;
    
    while (true) {
        sec++;
        
        //1. 뱀의 몸길이를 늘려 머리를 다음칸에 위치시킨다
        int head_x = snake.body.front().first+dx[snake.dir];
        int head_y = snake.body.front().second+dy[snake.dir];
        
        //2. 벽에 부딪힌 경우, 게임 끝
        if (head_x <= 0 || head_x > N || head_y <= 0 || head_y > N) return;
        //3. 몸에 부딪힌 경우, 게임 끝
        if (map[head_y][head_x] == 2) return;
        
        snake.body.push_front({head_x, head_y});
        
        //4. 이동한 칸에 사과가 있는 경우,
        if (map[head_y][head_x] == 1) {
            map[head_y][head_x] = 2;
        }
        
        //5. 이동한 칸에 사과가 없는 경우,
        else if (map[head_y][head_x] == 0) {
            map[head_y][head_x] = 2;
            int tail_x = snake.body.back().first;
            int tail_y = snake.body.back().second;
            snake.body.pop_back();
            map[tail_y][tail_x] = 0;
        }
        
        if (cmds.front().first == sec) {
            if (cmds.front().second == 'L') {
                snake.dir = (snake.dir - 1 + 4) % 4;
            } else {
                snake.dir = (snake.dir + 1) % 4;
            }
            cmds.pop();
        }
        
    }
}

int main(int argc, const char * argv[]) {
    cin >> N;
    cin >> K;
    for(int i=0; i<K; i++) {
        int y, x;
        cin >> y >> x;
        map[y][x] = 1;
    }
    cin >> L;
    for(int i=0; i<L; i++) {
        int X;
        char C;
        cin >> X >> C;
        cmds.push({X, C});
    }
    
    play_game();
    cout << sec << endl;
    
    return 0;
}

---

풀이 과정

풀이 시간 27분

#include <iostream>
#include <queue>
#include <deque>
using namespace std;

int N, K, L;

//map[y][x] = 2 -> 뱀의 몸이 있는 곳, map[y][x] = 1 -> 사과가 있는 곳, map[y][x] = 0 -> 빈 칸
int map[101][101] = {0, };

//방향 전환 정보, cmds[i] = {X, C}
queue<pair<int, char>> cmds;

//좌, 상, 우, 하
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

//게임 시간(초)
int sec = 0;

struct Snake {
	//뱀의 몸이 위치한 좌표들을 담는 덱
    deque<pair<int, int>> body = {{1, 1}};
    
    //뱀의 현재 방향
    int dir = 2;
};

Snake snake;

void play_game() {
	//뱀의 시작 위치 2로 표시
    map[1][1] = 2;
    
    while (true) {
        sec++;
        
        //1. 뱀의 몸길이를 늘려 다음 머리 위치를 구한다
        int head_x = snake.body.front().first+dx[snake.dir];
        int head_y = snake.body.front().second+dy[snake.dir];
        
        //2. 머리가 벽에 부딪힌 경우, 게임 끝
        if (head_x <= 0 || head_x > N || head_y <= 0 || head_y > N) return;
        //3. 머리가 자기 몸에 부딪힌 경우, 게임 끝
        if (map[head_y][head_x] == 2) return;
        
        //머리를 늘려 몸길이를 늘려준다
        snake.body.push_front({head_x, head_y});
        
        //4. 이동한 칸에 사과가 있는 경우, 몸길이가 증가된 상태로 유지한다
        if (map[head_y][head_x] == 1) {
        	//뱀의 머리가 위치한 곳을 2로 표시한다
            map[head_y][head_x] = 2;
        }
        
        //5. 이동한 칸에 사과가 없는 경우, 몸길이를 1 줄인다
        else if (map[head_y][head_x] == 0) {
        	//뱀의 머리가 위치한 곳을 2로 표시한다
            map[head_y][head_x] = 2;
            
            //뱀의 꼬리가 위치한 좌표를 가져오고 뱀의 꼬리를 자른다
            int tail_x = snake.body.back().first;
            int tail_y = snake.body.back().second;
            snake.body.pop_back();
            
            //뱀의 꼬리가 있던 자리를 빈 칸으로 바꿔준다
            map[tail_y][tail_x] = 0;
        }
        
        //현재 초가 끝난 시점
        //현재 초가 방향 전환 정보 X초와 같다면, 뱀의 방향을 전환한다
        if (cmds.front().first == sec) {
        	//왼쪽으로 90도 전환한다
            if (cmds.front().second == 'L') {
                snake.dir = (snake.dir - 1 + 4) % 4;
            }
            
            //오른쪽으로 90도 전환한다
            else {
                snake.dir = (snake.dir + 1) % 4;
            }
            
            cmds.pop();
        }
        
    }
}

int main(int argc, const char * argv[]) {
    cin >> N;
    
    //사과가 있는 좌표 받아오기
    cin >> K;
    for(int i=0; i<K; i++) {
        int y, x;
        cin >> y >> x;
        map[y][x] = 1;
    }
    
    //방향 전환 정보 받아오기
    cin >> L;
    for(int i=0; i<L; i++) {
        int X;
        char C;
        cin >> X >> C;
        cmds.push({X, C});
    }
    
    play_game();
    cout << sec << endl;
    
    return 0;
}

//시간복잡도 = O(n), 공간복잡도 = O(n)

 

 

---

이전 풀이

풀이 시간 1시간 30분

이 문제는 게임을 진행하면서 뱀과 보드를 어떻게 표현 해나갈지에 대한 고민이 핵심적인 것 같다.

뱀이 사과를 먹으면 몸 길이가 길어지고, 사과가 없는 칸으로 이동할 때는 몸 길이를 유지해야하기 때문에 꼬리를 이동시켜야 하는 부분을 어떻게 표현해야 할지 고민했는데 덱 Deque 자료구조를 사용하여 뱀을 표현할 수 있었다.

1. 사과가 있는 경우 -> 덱의 앞에 이동한 머리 위치를 추가한다.

2. 사과가 없는 경우 -> 덱의 front에 이동한 머리 위치를 추가하고, 덱의 back을 pop하여 꼬리 위치를 삭제한다.

 

가장 기본적으로 문제의 입력 사항을 보고 변수들을 적절하게 선언하고 초기화 해줘야 한다.

보드의 크기 N은 100이하라고 되어있었고, 보드는 NxN이며 보드의 맨 위 맨 좌측은 뱀의 시작점으로 (1, 1)부터 시작하기 위해 이차원 배열 map[101][101]을 선언하였다.

또한, 뱀의 방향 전환 횟수인 L이 100 이하로 주어진다 하여, 방향 전환 정보 (X, C)를 0번째 인덱스부터 담아 주기 위해 change[100][2]를 선언하였다.

뱀의 방향은 오른쪽 또는 왼쪽으로 바뀌며, 우, 하, 좌, 상 방향 순서대로 dx[4]와 dy[4]를 선언해주었다.

뱀의 방향이 오른쪽으로 회전하면 새 방향 인덱스 = (현재 방향 인덱스+1)%4를 해주고, 왼쪽으로 회전하면 새 방향 인덱스 = (현재 방향 인덱스+3)%4를 해주면 된다는 규칙을 찾았다.

따라서 방향 전환 정보를 받아올 때, C == 'L'이면 change[i][1] = 3, C=='R'이면 change[i][1] = 1로 초기화하여 방향 전환시에 계산이 용이하게 해주었다.

 

#include <iostream>
#include <deque>
using namespace std;

int map[101][101] = {0,};
int N, K, L;
int change[100][2] = {0, };

//+ -> 오른쪽 회전 D => (i+1)%4
//- -> 왼쪽 회전 L => (i+3)%4
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int timer = 0;

deque<pair<int, int>> snake;
int s_dir = 0;

void start_dummy(){
    //뱀의 시작 위치 초기화
    map[1][1] = 1;
    snake.push_back(make_pair(1, 1));
    int l = 0;
    while(1){
        //방향을 바꿔야 하는 경우
        if(l<=L-1 and change[l][0] == timer){
            s_dir = (s_dir + change[l][1])%4;
            l++;
        }
        timer ++;
        
        //머리 이동할 다음 칸
        int nx = snake.front().first + dx[s_dir];
        int ny = snake.front().second + dy[s_dir];
        //벽에 부딪힌 경우
        if(nx < 1 || nx > N || ny < 1 || ny > N) return;
        //자기 몸과 부딪힌 경우
        if(map[ny][nx] == 1) return;
        //사과가 있는 경우
        else if(map[ny][nx] == 4){
            //머리만 이동
            map[ny][nx] = 1;
            snake.push_front(make_pair(nx, ny));
        }
        //사과가 없는 경우
        else{
            //머리 이동
            map[ny][nx] = 1;
            snake.push_front(make_pair(nx, ny));
            //꼬리 이동
            pair<int, int> tail = snake.back();
            map[tail.second][tail.first] = 0;
            snake.pop_back();
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> N >> K;
    for(int i=0; i<K; i++){
        int x, y;
        cin >> y >> x;
        map[y][x] = 4;
    }
    cin >> L;
    for(int i=0; i<L; i++){
        char dir;
        cin >> change[i][0] >> dir;
        if(dir == 'L') change[i][1] = 3;
        else change[i][1] = 1;
    }
    
    start_dummy();
    cout << timer << endl;
    return 0;
}
//시간복잡도 = O(n), 공간복잡도 = O(n^2)