BOJ 3190 뱀

www.acmicpc.net/problem/3190

3190번: 뱀

 

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

deque를 사용하면 앞뒤로 삽입과 삭제를 용이하게 할 수 있다.

일단 방향을 정해주는데 북, 동, 서, 남을 차례로 0, 1, 2, 3으로 설정해준다.

이러면 dx, dy해주는 부분은

 

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

 

가 되고, 방향을 조절해주는 함수는 다음과 같이 쉽게 작성할 수 있다.

 

void dir(char C) {
	if (C == 'L') !d ? d = 3 : d--;
	else d == 3 ? d = 0 : d++;
}

 

처음에는 X와 C가 주어지면 X만큼 이동 후 C방향으로 회전시키는 것인 줄 알았는데

X가 현재 초를 가르키는 거라 고생 좀 했다.

 

우선 뱀이 움직이는 부분은 쉽게 구현 가능하다.

아무것도 아닌 부분은 '.', 뱀이 위치하고 있는 부분은 'o', 사과가 존재하는 부분은 '*'로 놓고

 

 

if (a[nx][ny] == '.') { //이동하려는 곳이 아무것도 아니라면
    dq.push_front({ nx,ny }); //덱에 넣어주고
    a[nx][ny] = 'o'; //o로 바꿔준다
    a[dq.back().first][dq.back().second] = '.'; //꼬리 부분은 다
    dq.pop_back();
}
else if (a[nx][ny] == '*') { //사과가 존재하면
    dq.push_front({ nx,ny });
    a[nx][ny] = 'o'; //꼬리는 떼지 않는다.
}

위처럼 구현하고 dir함수를 통해 방향을 바꿔준다.

 

이제 남은 구현부분은 이미 충돌했거나, 범위 밖을 벗어나는 경우 더 이상 X와 C를 받지 않고

빠져나와야 하는데 나는 뱀이 이동하는 bfs 함수를 boolean으로 작성하여 해결했다.

 

 

    bool go = true;
    for (int i = 0; i < l; ++i) {
        int x; char c; cin >> x >> c;
        go = query(x, c);
        if (!go) break;
    }
 
    if (!go) cout << t << endl;
    else {
        while (dq.front().first >= 0 && dq.front().first < n && dq.front().second >= 0 && dq.front().second < n) {
            ++t;
            if (a[dq.front().first+dx[d]][dq.front().second+dy[d]] == 'o') break;
            dq.push_front({ dq.front().first + dx[d],dq.front().second + dy[d] });
        }
        cout << t-1 << endl;
    }

 

만약 중간에 반복문을 빠져나온게 아니라 query를 전부 수행했다면

이제 벽에 박을 때까지 진행시켜주면 된다.

 

최종 코드

 

#include <iostream>
#include <deque>
using namespace std;
 
int n, k, l, d, t = 1;
char a[101][101];
deque<pair<int, int>> dq;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
 
void dir(char C) {
    if (C == 'L') !d ? d = 3 : d--;
    else d == 3 ? d = 0 : d++;
}
 
bool query(int x, char c) {
    for (; t <= x; ++t) {
        int nx = dq.front().first + dx[d];
        int ny = dq.front().second + dy[d];
        if (nx < 0 || nx >= n || ny < 0 || ny >= n) return false;
        if (a[nx][ny] == '.') {
            dq.push_front({ nx,ny });
            a[nx][ny] = 'o';
            a[dq.back().first][dq.back().second] = '.';
            dq.pop_back();
        }
        else if (a[nx][ny] == '*') { 
            dq.push_front({ nx,ny });
            a[nx][ny] = 'o';
        }
        else if (a[nx][ny] == 'o') return false;
    }
    dir(c);
    return true;
}
 
int main() {
    cin >> n >> k;
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= n; ++j)
            a[i][j] = '.';
 
    for (int i = 0; i < k; ++i) {
        int x, y; cin >> x >> y;
        a[x - 1][y - 1] = '*';
    }
    a[0][0] = 'o';
    dq.push_back({ 0,0 });
    d = 1; 
    
    cin >> l;
    bool go = true;
    for (int i = 0; i < l; ++i) {
        int x; char c; cin >> x >> c;
        go = query(x, c);
        if (!go) break;
    }
 
    if (!go) cout << t << endl;
    else {
        while (dq.front().first >= 0 && dq.front().first < n && dq.front().second >= 0 && dq.front().second < n) {
            ++t;
            if (a[dq.front().first+dx[d]][dq.front().second+dy[d]] == 'o') break;
            dq.push_front({ dq.front().first + dx[d],dq.front().second + dy[d] });
        }
        cout << t-1 << endl;
    }
 
    return 0;
}