[C++/3190] 뱀 - Implementation

문제

 

아이디어: 좌표를 저장하는 vector를 만들고, 사과가 없는 경우 꼬리를 자르기 위한 vector를 따로 만들어서 관리한다.

 

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int main()
{
    // N(보드 크기), K(사과 수), L(뱀 회전 수)
    int N, K, L;
    int result = 0;
    
    cin>>N;
    vector<vector<int>> v(N, vector<int>(N, 0));
    
    cin>>K;
    for(int i = 0;i < K;i++)
    {
        int a, b;
        cin>>a>>b;
        
        v[a - 1][b - 1] = 1;
    }
    
    vector<pair<int, char>> snake;
    cin>>L;
    for(int i = 0;i < L;i++)
    {
        int a;
        char b;
        cin>>a>>b;
        
        snake.push_back({a, b});
    }
    
    // 위치 좌표
    int i = 0;
    int j = 0;

    // snake가 방향을 전환할지 결정
    int index = 0;
    
    // 방향 전환 인덱스
    int dir = 0;
    
    // 꼬리 인덱스
    vector<pair<int, int>> tail;
    
    while(1)
    {
        result++;
        
        v[i][j] = -1;
        tail.push_back({i, j});
        
        if (result == snake[index].first + 1)
        {
            // 오른쪽 회전
            if (snake[index].second == 'D')
            {
                dir = (dir + 1) % 4;
            }
            // 왼쪽 회전
            else
            {
                dir--;
                if (dir < 0)
                    dir = 3;
            }
            
            index++;
        }
        
        int tempR = i + dx[dir];
        int tempC = j + dy[dir];
        
        // 벽인 경우는 종료
        if (tempR < 0 || tempC < 0 || tempR >= N || tempC >= N)
            break;
        
        // 이미 뱀이 있는 경우는 종료
        else if (v[tempR][tempC] == -1)
            break;
        
        // 사과가 있는 경우 몸의 길이를 늘림
        else if (v[tempR][tempC] == 1)
        {
            // nothing
        }
        
        // 사과가 없으면 꼬리를 잘라
        else if (v[tempR][tempC] == 0)
        {
            if (tail.size() >= 1)
            {
                int tailR = tail[0].first;
                int tailC = tail[0].second;
                
                v[tailR][tailC] = 0;

                tail.erase(tail.begin() + 0);
            }
        }
        
        i = tempR;
        j = tempC;
    }
    cout<<result<<endl;
    
    return 0;
}

 

 

// 2023.04.25 다시 푼 코드

 

#include <iostream>
 #include <vector>
 #include <queue>
 #include <algorithm>
 using namespace std;

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

int main() {
    int n, m;
    cin>>n>>m;
    
    vector<vector<int>> map(n, vector<int>(n, 0));
    for(int i = 0;i < m;i++) {
        int x, y;
        cin>>x>>y;
        
        map[x - 1][y - 1] = 1;
    }
    
    int L;
    cin>>L;
    queue<pair<int, int>> time;
    
    for(int i = 0;i < L;i++) {
        int x;
        char c;
        cin>>x>>c;
        
        time.push({x, c});
    }
    
    int dir = 0, count = 0;
    int headX = 0, headY = 0;
    map[headX][headY] = 2;
    
    queue<pair<int, int>> tail;
    tail.push({0, 0});
    while(1) {
        count++;
        int tempX = headX + dx[dir];
        int tempY = headY + dy[dir];
        
        // 벽
        if (tempX < 0 || tempY < 0 || tempX >= n || tempY >= n)
            break;
        
        // 자기자신
        if (map[tempX][tempY] == 2)
            break;
    
        if (map[tempX][tempY] == 0) {
            int tailX = tail.front().first;
            int tailY = tail.front().second;
            map[tailX][tailY] = 0;
            
            tail.pop();
        }
        
        headX = tempX;
        headY = tempY;
        tail.push({headX, headY});
        map[tempX][tempY] = 2;
        
        if (!time.empty() && count == time.front().first) {
            int change = time.front().second;
            
            if (change == 'L') {
                dir -= 1;
                if (dir < 0)
                    dir = 3;
            }
            else if (change == 'D') {
                dir = (dir + 1) % 4;
            }
            
            time.pop();
        }
    }
    
    cout<<count;
    
    return 0;
}

 

기본적인 풀이 방법은 변하지 않았는데 더 깔끔해지고 로직이 명확해졌음