백준 3190 - 뱀

문제

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

3190번: 뱀

 

 

풀이

문제에 나와있는 순서대로 구현을 해주면 된다. 특별히 신경 쓴 부분은 종료조건과 꼬리의 이동 부분이다. 

 

뱀의 몸이 있는 공간을 check 배열을 통해 나타냈다. check[x][y] = true 일 경우 x,y에는 뱀의 몸이 있는 것이다. 또한 뱀이 이동할 수 없는 벽도 check 배열을 통해 나타냈다. 따라서 check[x][y]=true 일 경우 x, y 좌표는 벽 또는 뱀의 몸을 의미한다. 뱀이 다음에 이동할 공간의 dx,dy 값에서 check[dx][dy] = true 일 경우 게임이 종료된다.

 

뱀이 이동할때 머리가 먼저 이동한 후 꼬리가 움직이는데, 꼬리에 해당하는 좌표 x,y 값을 이용해 check[x][y] = false로 해준다. 이때 현재 꼬리 좌표 값을 이동한 뱀의 꼬리 좌표 값으로 새로 갱신을 해줘야 한다. 이를 위해서 뱀의 머리가 이동할 때 다음에 이동할 좌표를 큐에 저장을 해준다. 그러면 큐에 저장된 좌표 값들은 뱀의 꼬리 좌표 값으로도 사용할 수 있게 된다. 큐에 있는 좌표를 이용해 뱀의 꼬리 값을 새로 갱신해준다.

 

---

 

뱀의 이동 경로를 좌표에 표시한다

- 빈 공간 좌표를 0

- 사과가 있는 좌표를 1

- 뱀이 이동한 좌표를 2

 

뱀의 이동 좌표들을 큐에 넣어서 관리하면 꼬리 쪽을 순서대로 뺄 수 있다 

큐에서 제거한 좌표는 다시 0으로 바꿔주면 된다

 

뱀의 머리쪽이 새로 이동할 좌표가 2면 뱀이 자기자신의 몸과 부딪힌 것이다

 

위 조건들을 지켜서 만들면 된다

 

코드

C++

#include <iostream>
#include <queue>
 
using namespace std;
 
int N, K, L;
int graph[101][101];
bool check[102][102];
int cnt;
int dx = 1, dy = 1;
int d = 1;
pair<int, int> head[4] = {{-1,0},{0,1},{1,0},{0,-1}};
queue<pair<int, int>> tail;
queue<pair<int, char>> change;
 
int right(int d)
{
    return (d + 1 > 3) ? 0 : d + 1;
}
 
int left(int d)
{
    return (d - 1 < 0) ? 3 : d - 1;
}
 
void solve()
{
    while (true)
    {
        dx += head[d].first;
        dy += head[d].second;
 
        if (check[dx][dy]) break;
 
        check[dx][dy] = true;
        tail.push({ dx, dy });
        
        if (graph[dx][dy])
            graph[dx][dy] = 0;
        else
        {
            check[tail.front().first][tail.front().second] = false;
            tail.pop();
        }
 
        cnt++;
 
        if (cnt == change.front().first)
        {
            if (change.front().second == 'D') d = right(d);
            else d = left(d);
            change.pop();
        }
    }
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> N >> K;
    for (int i = 0; i < K; i++)
    {
        int x, y;
        cin >> x >> y;
        graph[x][y] = 1;
    }
    cin >> L;
    for (int i = 0; i < L; i++)
    {
        int a; char b;
        cin >> a >> b;
        change.push({a, b});
    }
    for (int i = 0; i <= N + 1; i++)
        check[i][0] = check[i][N+1] = check[0][i] = check[N + 1][i] = true;
    
    check[dx][dy] = true;
    tail.push({dx,dy});
 
    solve();
 
    cout << cnt + 1;
    return 0;
}

 

python

from collections import deque
 
n = int(input())
k = int(input())
board = [[0 for _ in range(n)] for _ in range(n)]
for _ in range(k):
    r, c = map(int, input().split())
    board[r - 1][c - 1] = 1
 
event = deque()
l = int(input())
for _ in range(l):
    secs, rotate = input().split()
    event.append([int(secs), rotate])
 
snake = deque([[0, 0]])
time = 0
 
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
direction = 1
 
while True:
    time += 1
 
    head = snake[-1]
 
    new_head = [x + y for x, y in zip(head, [dy[direction], dx[direction]])]
 
    if not (0 <= new_head[0] < n and 0 <= new_head[1] < n and board[new_head[0]][new_head[1]] != 2):
        break
 
    if not board[new_head[0]][new_head[1]] == 1:
        del_y, del_x = snake.popleft()
        board[del_y][del_x] = 0
 
    board[new_head[0]][new_head[1]] = 2
    snake.append(new_head)
 
    if event and time == event[0][0]:
        rotate = event.popleft()[1]
        if rotate == 'L':
            direction = (direction - 1) % 4
        else:
            direction = (direction + 1) % 4
 
print(time)