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));

}

}


}



'Knowledge > 알고리즘' 카테고리의 다른 글

백준 13460번: 째로탈출2  (0) 2017.10.20
백준 12100번: 2048(Easy)  (0) 2017.10.19
백준 14499번: 주사위 굴리기  (0) 2017.10.19
백준 14502번: 연구소  (0) 2017.10.17
백준 14501번: 퇴사  (0) 2017.10.17

+ Recent posts