백준[3190] - 뱀

문제

백준 3190 문제 보기

접근 방법

시뮬레이션을 하는 문제이므로 문제에 쓰인 조건대로 진행하면 된다.

1. 뱀의 위치 정보, 시간, 현재 방향을 저장하는 뱀 구조체와 바뀌는 방향 정보를 담는 구조체 배열을 만들어 관리한다. 뱀의 몸통 정보는 배열보다는 헤드와 테일에 지속적인 삽입으로 벡터로 선언한다.
2. change_dir으로 현재 방향 기준 어떻게 방향을 바뀌는지 계산한다.
3. map과 snake_history의 이차원 배열을 두어 사과 및 뱀의 몸통을 확인한다. (snake_history을 두지 않고 뱀의 구조체에 위치 정보가 있으니 확인해도 된다. 하지만 조회를 하는데 시간이 걸린다.)
4. main에서는 문제에 따라 시물레이션을 돌려본다.

코드 및 주석 참조

코드

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

struct dir_info {
    int second;
    char direction;
};

struct snake {
    int time;
    int cur_direction;
    vector<pair<int, int>> body;
};

int N, K, L;
int map[100][100];
int snake_history[100][100];
dir_info dirInfo[100];

int change_dir(int current, char change_to) {
    // 동: 1 서: 3 남: 2 북: 0
    if(current == 0) {
        if(change_to == 'D') {
            current++;
            return current;
        } else {
            current = 3;
            return current;
        }
    } else if(current == 1) {
        if(change_to == 'D') {
            current++;
            return current;
        } else {
            current--;
            return current;
        }
    } else if(current == 2) {
        if(change_to == 'D') {
            current++;
            return current;
        } else {
            current--;
            return current;
        }
    } else if(current == 3) {
        if(change_to == 'D') {
            current = 0;
            return current;
        } else {
            current--;
            return current;
        }
    }
}

int main() {

    cin >> N;
    cin >> K;
    for(int i = 0; i < K; i ++) {
        int r, c;
        cin >> r >> c;
        map[r - 1][c - 1] = 1;
    }
    cin >> L;
    for(int i = 0; i < L; i ++){
        int second;
        char dir;
        dir_info temp;
        cin >> second >> dir;
        temp.second = second ;
        temp.direction = dir;
        dirInfo[i] = temp;
    }

    snake s;
    s.time = 0;
    // 동: 1 서: 3 남: 2 북: 0
    s.cur_direction = 1;
    // 위치 초기화
    s.body.push_back(make_pair(0, 0));
    // 방향 정보를 갖고있는 배열의 인덱스 정보
    int idx = 0;
    while(true) {
        int r = s.body[0].first;
        int c = s.body[0].second;
        int time = s.time;

        // 방향이 바뀌어야할 시간이라면 방향 전환 후 방향 정보 배열 인덱스 증가
        if(time == dirInfo[idx].second) {
            s.cur_direction = change_dir(s.cur_direction, dirInfo[idx].direction);
            idx ++;
        }

        // 동
        if(s.cur_direction == 1) {
            int nextR = r;
            int nextC = c + 1;
            // 다음 방문할 위치가 뱀의 몸통이거나 맵 밖으로 나가면 조건문 탈출
            if(snake_history[nextR][nextC] == 1 || nextR >= N || nextC >= N || nextC < 0 || nextR < 0) {
                break;
            }
            // 머리 추가
            s.body.insert(s.body.begin(), make_pair(nextR, nextC));
            // 뱀의 지도에서 추가
            snake_history[nextR][nextC] = 1;
            // 사과가 없다면
            if(!map[nextR][nextC]) {
                int xR = s.body.back().first;
                int xC = s.body.back().second;
                // 뱀의 지도에서 위치 삭제
                snake_history[xR][xC] = 0;
                // 구조체에서도 위치 정보 삭제
                s.body.pop_back();
            } else {
                // 사과가 있다면 사과만 지우고 몸통은 유지
                map[nextR][nextC] = 0;
            }
        } else if(s.cur_direction == 0) {
            int nextR = r - 1;
            int nextC = c;
            if(snake_history[nextR][nextC] == 1 || nextR >= N || nextC >= N || nextC < 0 || nextR < 0) {
                break;
            }
            s.body.insert(s.body.begin(), make_pair(nextR, nextC));
            snake_history[nextR][nextC] = 1;
            if(!map[nextR][nextC]) {
                int xR = s.body.back().first;
                int xC = s.body.back().second;
                snake_history[xR][xC] = 0;
                s.body.pop_back();
            } else {
                map[nextR][nextC] = 0;
            }
        } else if(s.cur_direction == 2) {
            int nextR = r + 1;
            int nextC = c;
            if(snake_history[nextR][nextC] == 1 || nextR >= N || nextC >= N || nextC < 0 || nextR < 0) {
                break;
            }
            s.body.insert(s.body.begin(), make_pair(nextR, nextC));
            snake_history[nextR][nextC] = 1;
            if(!map[nextR][nextC]) {
                int xR = s.body.back().first;
                int xC = s.body.back().second;
                snake_history[xR][xC] = 0;
                s.body.pop_back();
            } else {
                map[nextR][nextC] = 0;
            }
        } else if(s.cur_direction == 3) {
            int nextR = r;
            int nextC = c - 1;
            if(snake_history[nextR][nextC] == 1 || nextR >= N || nextC >= N || nextC < 0 || nextR < 0) {
                break;
            }
            s.body.insert(s.body.begin(), make_pair(nextR, nextC));
            snake_history[nextR][nextC] = 1;
            if(!map[nextR][nextC]) {
                int xR = s.body.back().first;
                int xC = s.body.back().second;
                snake_history[xR][xC] = 0;
                s.body.pop_back();
            }else {
                map[nextR][nextC] = 0;
            }
        }
        s.time ++;
    }
    cout << s.time + 1;
    return 0;
}