백준 3190번: 뱀

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.Hashtable;

import java.util.LinkedList;

import java.util.Queue;

import java.util.StringTokenizer;

class Snake {

Queue<Integer> body = new LinkedList<>();

// 해당 위치로 움직인다.

void move(int where, boolean hasApple) {

if (hasApple) {

body.add(where);

} else {

body.poll();

body.add(where);

}

}

// 자기 자신에 충돌하는지 체크한다.

boolean isSelf(int where) {

return body.contains(where);

}

}

public class Main {

private static boolean Debug = false;

private static int MapSize;

private static int[][] Map;

private static Hashtable<Integer, Character> comMap;

private static Snake snake = new Snake();

public static void main(String[] args) throws Exception {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

StringTokenizer st;

// 맵 크기, 사과 개수

MapSize = Integer.parseInt(br.readLine());

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

// 맵 생성

Map = new int[MapSize][];

for (int i = 0; i < MapSize; i++) {

Map[i] = new int[MapSize];

}

// 사과 위치 배정

int y, x;

for (int i = 0; i < AppSize; i++) {

st = new StringTokenizer(br.readLine());

y = Integer.parseInt(st.nextToken()) - 1;

x = Integer.parseInt(st.nextToken()) - 1;

Map[y][x] = 1;

}

// 커맨드 읽기

comMap = new Hashtable();

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

int time;

char direct;

for (int i = 0; i < cSize; i++) {

st = new StringTokenizer(br.readLine());

time = Integer.parseInt(st.nextToken());

direct = st.nextToken().charAt(0);

comMap.put(time, direct);

}

// 위치 초기화, 시간 초기화

y = x = 0;

rIndex = 1;

timer = 0;

// 뱀이 움직인다.

snake.move(0, false);

findPath();

// 시간 출력

System.out.println(timer);

}

static int[] rotY = { -1, 0, 1, 0 };

static int[] rotX = { 0, 1, 0, -1 };

static int y, x;

static int rIndex;

static int timer;

private static void findPath() {

// 해당 시간에 방향 전환이 발생하는가?

if (comMap.containsKey(timer)) {

char direct = comMap.get(timer);

// 왼쪽 회전 =>  rIndex--;  // 오른쪽 회전 => rIndex++;

if (direct == 'L') {

rIndex = rIndex == 0 ? 3 : rIndex - 1;

} else {

rIndex = rIndex == 3 ? 0 : rIndex + 1;

}

comMap.remove(timer);

}

// 움직임이 시작되는 순간

timer++;

// 움직이려는 방향이 맞다면 움직인다.

if (isVaild(rIndex)) {

y += rotY[rIndex];

x += rotX[rIndex];

int where = y * MapSize + x;

// 자신의 몸에 충돌하는가?

if (snake.isSelf(where)) {

return;

}

// 사과가 있다면

if (Map[y][x] == 1) {

Map[y][x] = 0;

snake.move(where, true);

} else { // 사과가 없다면

snake.move(where, false);

}

findPath();

} else {

// 움직이는 방향이 맵 밖인 경우, 이탈한다.

return;

}

}

// 해당 방향이 맵의 범위를 초과하는지를 판단한다.

private static boolean isVaild(int index) {

switch (index) {

case 0:

return y - 1 >= 0;

case 2:

return y + 1 < MapSize;

case 1:

return x + 1 < MapSize;

case 3:

return x - 1 >= 0;

}

return false;

}

public static void log(String input) {

if (Debug) {

System.out.println(input);

}

}

public static void log(String input, Object... args) {

if (Debug) {

System.out.println(String.format(input, args));

}

}

}