[백준/Baekjoon] 3190 뱀 C++ :: Implementation

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

3190번: 뱀

---

1. Logic

주어진 규칙에 맞춰 그대로 구현하면 됨.

뱀의 머리와 길이까지의 좌표를 저장하는 덱을 생성해서 넣다뺐다 해주면 됨.

1. 덱에 다음에 머리가 갈 좌표를 front에 넣어줌 + 이동 횟수 1 올려주기

2. 게임에서 지게되는 조건 확인

3. 머리가 이동한 곳 방문 처리하여 뱀이 있는곳 표시(이걸 2번보다 먼저하면 항상 게임에서 지게되는 조건이 만들어짐)

4. 머리가 이동한 곳에 사과가 없으면 꼬리를 없애주기 // 사과가 있으면 꼬리를 유지하고 사과만 없애주기

5. 방향을 바꾸는 커맨드가 있을경우 확인해서 방향 변경

 

이 정도가 로직일 것 같다. 거의 수도코드인데?

---

2. Code

#include <bits/stdc++.h>

using namespace std;

bool vis[101][101];
bool apple[101][101];

deque<pair<int, int>> snake;
queue<pair<int, char>> cmd;

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

int n, k, l;

int start() {
    int cnt = 0;
    int dir = 2;
    
    vis[0][0] = true;
    snake.push_front({0, 0});
    
    while(true) {
        //뱀 옮기기
        int nx = snake.front().second + dx[dir];
        int ny = snake.front().first + dy[dir];
        snake.push_front({ny, nx});
        cnt++;
        
        //게임에서 지게되는 조건
        if(ny < 0 || nx < 0 || ny >= n || nx >= n) {
            break;
        }
        if(vis[ny][nx]) break;
        
        //이게 앞에 가면 뱀 머리랑 겹쳐서 바로 끝남
        vis[ny][nx] = true;
        
        //사과에 대한 조건
        if(!apple[ny][nx]) {
            int tailX = snake.back().second;
            int tailY = snake.back().first;
            vis[tailY][tailX] = false;
            snake.pop_back();
        }
        else {
            //사과 먹었으면 없애주기
            apple[ny][nx] = false;
        }
        
        if(cmd.front().first == cnt) {
            if(cmd.front().second == 'D') {
                dir = (dir+1) % 4;
            }
            else {
                dir = (dir+3) % 4;
            }
            cmd.pop();
        }
        
    }
    
    return cnt;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n >> k;
    
    for(int i = 0; i < k; i++) {
        int y, x;
        cin >> y >> x;
        
        apple[y-1][x-1] = true;
    }
    
    cin >> l;
    
    for(int i = 0; i < l; i++) {
        int t;
        char command;
        
        cin >> t >> command;
        
        cmd.push({t, command});
    }
    
    cout << start();
}

3.Feedback

깃허브에 커밋하다가 확인했는데 이전에 풀다가 실패한 코드를 봤다. 코드도 이상하게 짰던데 전보다 성장한 것 같아 기분이 너무 좋다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90