Java - [BOJ]3190 - 뱀

출처

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

 

문제

 

뱀이 진행하던 중 사과를 만나면 몸길이가 하나 추가된다. 사과가 없다면 몸길이는 변화없이 앞으로만 전진하며, 'D'를 만나면 오른쪽으로, 'L'을 만나면 왼쪽으로 방향을 바꾼다.

 

위 조건에 따라 뱀 게임을 진행하며, 머리나 몸에 부딪힐때 게임이 종료된다.

 

풀이

특별한 알고리즘이 아닌, 구현, 시뮬레이션 문제이다.

 

직접 문제 조건에 따라 진행되도록 코드를 구현하면 된다.

 

시간을 늘려가며 while문에서 게임을 진행하고, 조건이 충족되면 게임을 종료하도록 한다.

 

while문 안에서는 다음과 같은 순서로 진행된다.

while (true) {
	- time 증가
    - 뱀의 머리를 큐에서 빼서, 앞으로 한칸 전진시킴
    - 벽에 부딪히거나 몸에 부딪히면 게임 종료
    - 사과를 만나면 꼬리를 그대로 두고, 아니라면 꼬리를 하나 제거
    - 회전하라는 명령이 있다면, 방향을 회전시킴
}

 

코드

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

public class Main {
	static int N, K;
	static int[][] world;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static Deque<int[]> snake = new ArrayDeque<>();
    static Map<Integer, String> info = new HashMap<>();
    


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(br.readLine());
        world = new int[N+1][N+1];

        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            world[r][c] = 1;
        }
        snake.add(new int[]{1, 1});

        int L = Integer.parseInt(br.readLine());

        for (int i = 0; i < L; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            String d = st.nextToken();

            info.put(x, d);
        }

        int time = 0;
        int now_d = 0;
        while(true) {
            time++;

            int[] now = snake.peek();
            int[] nnow = new int[]{now[0] + dx[now_d], now[1] + dy[now_d]};


            if (!isRange(nnow) || isDead(nnow)) {
                break;
            }
            snake.addFirst(nnow);
            
            if (world[nnow[0]][nnow[1]] == 1) {
                world[nnow[0]][nnow[1]] = 0;
            } else {
                int[] tmp = snake.pollLast();
            }

            if (info.containsKey(time)) {
                now_d = changeD(now_d, info.get(time));
            }
            
        }

        bw.write(time + "\n");


        br.close();
        bw.flush();
        bw.close();
    }

    public static boolean isDead(int[] now) {
        for (int[] x : snake) {
            if (x[0] == now[0] && x[1] == now[1]) {
                return true;
            }
        }
        return false;
    }

    public static boolean isRange(int[] now) {
        return now[0] > 0 && now[0] <= N && now[1] > 0 && now[1] <= N;
    }

    public static int changeD(int d, String x) {
        if (x.equals("L")) {
            return (4 + (d - 1)) % 4;
        } else {
            return (d + 1) % 4;
        }
    }

}