백준 3190번. 뱀 (Java, Python)

Problem

• 문제 링크

사과의 위치와 뱀의 이동 경로가 주어질 때 게임이 끝나는 초(second)를 구하는 문제입니다.

Solution

특별한 알고리즘은 사용하지 않고 문제에서 제시한 대로 구현만 하는 시뮬레이션 문제입니다.

조건을 살펴보면

1. 뱀의 머리는 무조건 이동한다
2. 뱀의 머리가 있는 곳에 사과가 있으면 꼬리 위치는 그대로
3. 뱀의 머리가 있는 곳에 사과가 없으면 없으면 꼬리를 잘라낸다.
4. 뱀의 머리가 있는 곳에 벽이나 뱀의 몸이 있다면 게임이 끝난다.

이렇게 총 4가지의 조건을 구현하면 됩니다.

오른쪽 왼쪽으로 방향을 바꾸는 건 % 연산자를 사용하면 쉽게 할 수 있습니다.

왼쪽으로 돌리기 = (현재 방향 + 3) % 4

오른쪽으로 돌리기 = (현재 방향 + 1) % 4

대신 처음 dx, dy 배열을 북, 동, 남, 서 순서처럼 시계방향 또는 반시계 방향으로 설정해야 합니다.

인덱스가 0, 1, 2, 3 에서 반복된다는 점을 활용하면 % 4 연산자를 통해 다음 방향 인덱스를 쉽게 구할 수 있습니다.

뱀의 몸통을 기억하는 방법은 Deque 자료구조를 사용하였습니다.

Deque는 Queue나 Stack과 달리 리스트의 앞, 뒤에서 삽입/삭제가 가능한 자료구조입니다.

Deque 자체를 뱀의 몸이라고 생각하면서 꼬리를 삭제할때는 removeLast(), 머리를 이동시킬때는 addFirst()를 사용하면 됩니다.

Java Code

import java.util.*;
import java.io.*;

class Main {
    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    static class Dot {
        int x, y;

        public Dot(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static int n;
    static int K;
    static int[][] map;
    static int L;
    static int[] time;
    static int[] dir;
    static int[] dx = {-1, 0, 1, 0};    // 북동남서
    static int[] dy = {0, 1, 0, -1};
    static Deque<Dot> snake = new ArrayDeque<Dot>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = stoi(br.readLine());
        K = stoi(br.readLine());
        map = new int[n + 1][n + 1];    // 맨 위 맨 좌측은 (1,1)

        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());

            int v1 = stoi(st.nextToken());
            int v2 = stoi(st.nextToken());
            map[v1][v2] = 1;    // 사과 위치는 1
        }

        L = stoi(br.readLine());
        time = new int[L];
        dir = new int[L];

        for (int i = 0; i < L; i++) {
            st = new StringTokenizer(br.readLine());

            time[i] = stoi(st.nextToken());
            dir[i] = getDirection(st.nextToken());
        }

        // 문제 풀이
        solution();
    }

    static void solution() {
        int second = 0;
        int snakeDir = 1;    // 첫 방향은 오른쪽
        int timeIdx = 0;
        map[1][1] = 2;  // 처음 뱀의 위치는 (1,1)
        snake.add(new Dot(1, 1));

        while (true) {
            // 시간이 지나면 방향 바꾸기
            if (timeIdx < L && time[timeIdx] == second) {
                snakeDir = (snakeDir + dir[timeIdx]) % 4;
                timeIdx++;
            }

            // 1. 몸길이를 늘려 머리를 다음 칸에 위치시킨다
            int nx = snake.getFirst().x + dx[snakeDir];
            int ny = snake.getFirst().y + dy[snakeDir];

            // 몸이나 벽과 부딪히면 게임 끝
            if (nx <= 0 || nx > n || ny <= 0 || ny > n) {
                System.out.println(second + 1);
                break;
            }
            if (map[nx][ny] == 2) {
                System.out.println(second + 1);
                break;
            }

            if (map[nx][ny] == 1) {
                // 2. 만약 이동한 칸에 사과가 있다면, 사과 없어지고 꼬리 그대로 머리 추가
                map[nx][ny] = 2;
                snake.addFirst(new Dot(nx, ny));
            }
            else if (map[nx][ny] == 0) {
                // 3. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여 꼬리가 위치한 칸 비우기
                map[nx][ny] = 2;
                snake.addFirst(new Dot(nx, ny));

                Dot tail = snake.removeLast();
                map[tail.x][tail.y] = 0;
            }

            second++;
        }
    }

    // 오른쪽은 1 왼쪽은 3
    static int getDirection(String s) {
        if (s.equals("D"))
            return 1;
        else
            return 3;
    }
}

Python Code

# -*- coding: utf-8 -*-
 
import sys
import collections
 
N = 0
arr = []
## 북 동 남 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
snakes = collections.deque([[1,1]])
 
def printX():
    print()
    for i in range(1, N+1):
        for j in range(1, N+1):
            print(arr[i][j], end=" ")
        print()
 
 
def snake_move(direction):
    [x, y] = snakes[0]
    
    nx = x + dx[direction]
    ny = y + dy[direction]
 
    ## 머리가 몸통에 부딪히면 종료
    if [nx, ny] in snakes:
        return True
    
    ## 벽에 부딪히면 종료
    if nx <= 0 or nx > N or ny <= 0 or ny > N:
        return True
 
    ## 이동한 칸에 아무것도 없으면 꼬리를 줄여줌
    if arr[nx][ny] == 0:
        [ex, ey] = snakes.pop()
        arr[ex][ey] = 0
 
    ## 이동한 칸에 사과가 있으면 없애고 몸을 늘린다
    snakes.appendleft([nx, ny])
    arr[nx][ny] = 1
 
    return False
 
 
def rotate(s, d):
    ## L이면 왼쪽 D면 오른쪽
    if s == "L":
        return (d+3)%4
    else:
        return (d+1)%4
 
def solve(move, L):
    idx = 0
    direction = 1     ## 초기 방향은 오른쪽
    time = 0
 
    while True:
        if idx < L:
            if move[idx][0] == time:
                direction = rotate(move[idx][1], direction)
                idx += 1
 
        if snake_move(direction) == True:
            print(time+1)
            return
 
        time += 1
 
 
if __name__ == '__main__':
    N = int(sys.stdin.readline())
    K = int(sys.stdin.readline())
    arr = [[0]*(N+1) for i in range(N+1)]
 
    for i in range(K):
        v1, v2 = map(int, sys.stdin.readline().split())
        arr[v1][v2] = 2
    
    L = int(sys.stdin.readline())
 
    move = []
    for i in range(L):
        X, C = sys.stdin.readline().split()
        move.append([int(X), C])
 
    ## 처음 뱀 위치
    arr[1][1] = 1
    solve(move, L)