백준 알고리즘 3190: 뱀(Python, c++)

 

3190번: 뱀

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

문제

---

문제 해결을 위한 과정

가장 먼저 주의해야 할 점은 보드의 맨 위 좌측의 좌표가 0행 0열이 아닌 1행 1열이라는 점입니다. 따라서 사과의 위치를 입력을 받은 후 일반적으로 사용하는 행, 열의 위치에 사과를 저장하기 위해 입력된 좌표에서 각각 1씩 빼서 보드에 사과를 집어넣어야 합니다. 단순하게 문제의 조건을 따라만 가면 그다지 어려운 문제는 아닙니다. 뱀이 바라보는 방향을 기준으로 한 칸씩 이동을 하게 되는데 몸길이가 늘려 머리가 다음칸에 가게 됩니다. 다음칸이 벽이거나 꼬리가 있는 부분이 아닌 한 머리가 속한 칸이 사과가 없는 칸이면 꼬리가 한 칸 앞으로 이동을 해야 합니다. 따라서 뱀이 현재 위치한 좌표들로 리스트를 만든 후 뱀이 머리가 닿는 부분을 리스트에 append 하게 되면 반대로 꼬리의 부분은 리스트의 맨 앞부분일 것입니다. 따라서 해당 리스트의 맨 앞을 pop 해주게 되면 쉽게 꼬리를 한 칸 앞으로 이동해줄 수 있습니다. 비록 리스트의 pop이 O(N)의 시간 복잡도를 가지더라도 이 문제에서는 통과할 수 있습니다. 

---

문제 해결을 위한 팁

이 문제를 풀때 신경 써야 할 부분은 바로 방향에 관한 부분입니다. 보통 방향에 관한 부분이 문제에서 나오면 dx, dy로 각각의 방향 리스트를 만드는 것이 일반적입니다. 맨 처음 뱀이 바라보고 있는 부분이 오른쪽 즉 동쪽이기 때문에 동쪽을 리스트의 0번째 리스트로 입력을 한 후 반 시계 방향으로 동쪽, 북쪽, 서쪽, 남쪽으로 방향을 설정하면 dx, dy는 다음과 같습니다.

dx = [0, -1, 0, 1]

dy = [1, 0, -,1 0]

이 좌표는 수학적 의미의 x, y좌표가 아닌 프로그래밍에서의 행, 열의 의미입니다. 동쪽 즉 오른쪽으로 움직이는 경우 행은 그대로지만 열이 하나 증가하기 때문에 dx, dy의 0번째 인덱스가 0, 1 입니다. 이렇게 하면 기존의 좌표를 x, y 다음 과표를 nx, ny라 지정하면 

nx = x + dx[0]

ny = y + dy[0]

이처럼 지정할 수 있습니다. 이번엔 표를 보고 생각해봅시다.

방향(리스트에서의 인덱스 값)	D 인 경우(리스트에서의 인덱스 값)	L 인 경우(리스트에서의 인덱스 값)
동쪽(0)	남쪽(3)	북쪽(1)
북쪽(1)	동쪽(0)	서쪽(2)
서쪽(2)	북쪽(1)	남쪽(3)
남쪽(3)	서쪽(2)	동쪽(0)

위 표를 보고 기존 방향이 dir일 경우 다음과 같음을 알 수 있습니다.

D인 경우 dir = (dir - 1) % 4

L인 경우 dir = (dir + 1) % 4 

---

소스코드 - python

 

N = int(input())
graph = [[0]*N for _ in range(N)]
apple = int(input())
movement = []
for i in range(apple):
  a, b = map(int, input().split())
  graph[a-1][b-1] = 1 # 문제에서 맨 좌측 위가 1, 1 이라고 하였기 때문
 
move = int(input())
for i in range(move):
  a, b = input().split()
  movement.append((int(a), b))
 
# 동, 북, 서, 남
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
 
def turn(dir, x): # 다음 방향을 정하는 함수
  if x == 'D':
    dir = (dir -1) % 4
  elif x == 'L':
    dir = (dir+1) % 4
  return dir
 
def game():
  x = 0; y = 0
  graph[x][y] = 2 # 맨 처음 뱀이 0, 0 에 있으므로 해당 지역을 뱀이 있는것으로 표시
  snake = [(x, y)] # 뱀의 현재 좌표를 담는 리스트
  count = 0
  dir = 0 # 맨 처음 방향인 동쪽을 0으로 설정
  index = 0
  while True:
    nx = x + dx[dir]
    ny = y + dy[dir]
    if 0 <= nx < N and 0 <= ny < N and graph[nx][ny] != 2:  # 벽이 아니거나 뱀이 있는 지역이 
      if graph[nx][ny] == 0: # 사과 없는 지역인 경우
        count += 1
        graph[nx][ny] = 2
        snake.append((nx, ny))
        prev_x, prev_y = snake.pop(0)
        graph[prev_x][prev_y] = 0
      elif graph[nx][ny] == 1: #사과 있는 지역
        count += 1
        graph[nx][ny] = 2
        snake.append((nx, ny))
      if index < move and count == movement[index][0]:
        dir = turn(dir, movement[index][1])
        index += 1
      x = nx
      y = ny
    else:
      return count
 
print(game()+1)

---

소스코드 - c++

#include <bits/stdc++.h>
#define MAX 101
 
using namespace std;
int n, k;
int graph[MAX][MAX];
int l;
queue<pair<int, char>> dir;
queue<pair<int, int>> snake;
int direction;
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
 
int moveDirection(int direction, char dInfo) {
    if (direction == 0) {
        if (dInfo == 'L')
            return 2;
        else
            return 3;
    }
    else if (direction == 1) {
        if (dInfo == 'L')
            return 3;
        else
            return 2;
    }
    else if (direction == 2) {
        if (dInfo == 'L')
            return 1;
        else
            return 0;
    }
    else {
        if (dInfo == 'L')
            return 0;
        else
            return 1;
    }
}
 
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    cin >> k;
    for (int i = 0; i < k; i++) {
        int a, b;
        cin >> a >> b;
        graph[a - 1][b - 1] = 1;
    }
 
    cin >> l; 
    for (int i = 0; i < l; i++) {
        int a;
        char c;
        cin >> a >> c;
        dir.push(make_pair(a, c));
    }
 
    int time = 1;
    direction = 3;
    int xPos = 0, yPos = 0;
    graph[xPos][yPos] = 2;
    snake.push(make_pair(xPos, yPos));
    int tInfo = dir.front().first;
    char dInfo = dir.front().second;
    dir.pop();
 
    while (true) {
        xPos += dx[direction];
        yPos += dy[direction];
        if (xPos < 0 || yPos < 0 || xPos >= n || yPos >= n) {
            break;
        }
        if (graph[xPos][yPos] == 2) {
            break;
        }
        snake.push(make_pair(xPos, yPos));
        if (graph[xPos][yPos] != 1) { // 사과없는 경우
            int x = snake.front().first;
            int y = snake.front().second;
            graph[x][y] = 0;
            snake.pop();
        }
        if (graph[xPos][yPos] == 0) { // 사과 있는 경우
            graph[xPos][yPos] = 0;
        }
        graph[xPos][yPos] = 2;
        if (time == tInfo) {
            direction = moveDirection(direction, dInfo);
            if (!dir.empty()) {
                tInfo = dir.front().first;
                dInfo = dir.front().second;
                dir.pop();
            }
        }
        time++;
    }
    
    cout << time;
    return 0;
}