BOJ 3190 · 뱀

알고리즘 분류 : 시뮬레이션  

주어진 조건을 그대로 구현하는 시뮬레이션 문제다. 뱀이 사과를 먹으면서 길이를 늘리는 게임을 구현해야 한다.

• 뱀의 시작 위치는 (0, 0)이며 시작 방향은 오른쪽이다. 범위 (0, 0) ~ (N-1, M-1) 기준
• 뱀의 이동 좌표를 저장하기 위해 Queue를 사용한다.
• 매초, 뱀이 현재 방향으로 머리를 먼저 한 칸 앞으로 옮긴다. 머리 위치를 큐에 push 한다.
• 이동한 칸에 사과(1)가 있을 경우, 꼬리를 줄이지 않는다.
• 이동한 칸이 빈칸(0)이라면, 꼬리를 한 칸 줄인다. 큐에서 꼬리 칸을 pop 한다.
• 뱀의 좌표는 (2)로 둔다.
• 이동 후에, 방향 전환을 해야 한다면, 주어진 입력에 따라 방향을 바꾼다.
• 이동할 때 벽에 부딪히거나(맵을 벗어난 경우), 뱀 자신(2)에게 부딪히면 종료한다.
• 그렇지 않다면 시간을 1초 증가시키고, 위 과정을 반복한다.

---

C++ 소스코드

#include <cstdio>
#include <queue>
using namespace std;

int n, k, m;
int x, y, z, d, ans;
int a[100][100], t[101];
char c[101];
const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
const int L[] = {3, 2, 0, 1}, D[] = {2, 3, 1, 0};
queue<pair<int, int>> q;

void solve() {
    a[0][0] = 2;
    q.push({0, 0});
    while (true) {
        x += dx[d], y += dy[d];
        ans++;
        if (x < 0 || x >= n || y < 0 || y >= n || a[x][y] == 2) {
            printf("%d\n", ans);
            return;
        }
        if (a[x][y] == 0) {
            int nx = q.front().first, ny = q.front().second; q.pop();
            a[nx][ny] = 0;
        }
        a[x][y] = 2;
        q.push({x, y});
        if (ans == t[z]) {
            if (c[z] == 'L') d = L[d];
            else d = D[d];
            z++;
        }
    }
}

int main() {
    scanf("%d %d", &n, &k);
    for (int i=0; i<k; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        a[u-1][v-1] = 1;
    }
    scanf("%d", &m);
    for (int i=0; i<m; i++) {
        scanf("%d %c", &t[i], &c[i]);
    }
    solve();
    return 0;
}

---

Python 3 소스코드

from collections import deque
dx, dy = (0, 0, 1, -1), (1, -1, 0, 0)
L, D = (3, 2, 0, 1), (2, 3, 1, 0)

def solve():
    x, y, z, d, ans = 0, 0, 0, 0, 0
    a[0][0] = 2
    q = deque()
    q.append((0, 0))
    while True:
        x, y = x+dx[d], y+dy[d]
        ans += 1
        if x < 0 or x >= n or y < 0 or y >= n or a[x][y] == 2:
            print(ans)
            return
        if not a[x][y]:
            nx, ny = q.popleft()
            a[nx][ny] = 0
        a[x][y] = 2
        q.append((x, y))
        t, c = b[z]
        if ans == int(t):
            if c == 'L':
                d = L[d]
            else:
                d = D[d]
            z = (z+1)%m

n = int(input())
a = [[0]*n for _ in range(n)]
for _ in range(int(input())):
    u, v = map(int, input().split())
    a[u-1][v-1] = 1
m = int(input())
b = [list(map(str, input().split())) for _ in range(m)]
solve()

---

참고

• 백준 온라인 저지 : BOJ 3190