[구현 알고리즘] 뱀 ★★☆

기출 : 삼성 SW 역량테스트

 

문제를 처음 보고 꼬리와 머리 좌표, 머리의 방향을 저장하는 snake 구조체를 생각해 냈다

 

코드를 작성하다 보니 꼬리의 방향, 즉 몸통의 좌표가 필요한 것을 알았다

 

뱀이 사과를 먹으면 꼬리는 그대로 있고 머리만 한칸 추가된다

 

만약 사과가 없다면 꼬리가 사라지고 머리는 추가된다

 

머리쪽은 항상 추가되고 꼬리쪽은 항상 삭제되므로 추가, 삭제 방향이 정해진 Queue를 사용해야 한다

 

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
int n, k, l;
int board[101][101];
int t;
int dir = 100;
vector<pair<int, int>> mov;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 0;i < k;i++) {
        int x, y;
        cin >> x >> y;
        board[x][y] = 1;
    }
    cin >> l;
    for (int i = 0;i < l;i++) {
        int a; char c;
        cin >> a >> c;
        if (c == 'D') mov.push_back({ a,1 });
        else mov.push_back({ a,-1 });
    }
    queue<pair<int, int>> snake;
    snake.push({1,1});
    board[1][1] = -1;
    while (true) {
        for (int i = 0;i < l;i++) {       // 방향변환 하나씩 뽑는다
            while (t != mov[i].first) {       // 방향변환 할때까지 계속 진행 
                int mx = snake.back().X + dx[dir % 4];
                int my = snake.back().Y + dy[dir % 4];
                if (mx < 1 || my < 1 || mx > n || my > n || board[mx][my] == -1) {
                    cout << t+1; return 0;
                }
                if (board[mx][my] == 1) {       // 사과 만나면
                    snake.push({ mx,my });
                    board[mx][my] = -1;
                    t++;
                }
                else {                       // 빈 공간이면   
                    board[snake.front().X][snake.front().Y] = 0;
                    board[mx][my] = -1;
                    snake.push({ mx, my });
                    snake.pop();
                    t++;
                }
                
            }
            dir += mov[i].second;
        }
    }
	return 0;
}