[백준] 자바 문제 풀이 3190 : 골드4

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
	static class Point{
		int x;
		int y;
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		int[][] area = new int[n][n]; // snake : 1, apple : 2, blank : 0

		int snake = Integer.parseInt(br.readLine());
		for (int i = 0; i < snake; i++) {
			StringTokenizer str = new StringTokenizer(br.readLine(), " ");
			int apple_i = Integer.parseInt(str.nextToken());
			int apple_j = Integer.parseInt(str.nextToken());
			area[apple_i-1][apple_j-1] = 2;
		}

		int m = Integer.parseInt(br.readLine());
		int[] time = new int[m];
		char[] action = new char[m];
		for (int i = 0; i < m; i++) {
			StringTokenizer str = new StringTokenizer(br.readLine(), " ");
			time[i] = Integer.parseInt(str.nextToken());
			action[i] = str.nextToken().charAt(0);
		}

		area[0][0] = 1; // 초기 뱀 위치
		int[][] delta = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
		int sec = 0;
		boolean end = false;
		int tidx = 0;
		int dir = 0;

		Deque<Point> p = new ArrayDeque<>();
		p.add(new Point(0,0));
		while (!end) {
			//이동
			int dx = p.peekFirst().x + delta[dir][0];
			int dy = p.peekFirst().y + delta[dir][1];
			
			if(dx >= 0 && dx < n && dy >=0 && dy < n) {
				if(area[dx][dy] == 1) {
					end = true;
				}
				else if(area[dx][dy] == 2) {
					p.addFirst(new Point(dx, dy));
					area[dx][dy] = 1;
				}
				else {
					p.addFirst(new Point(dx, dy));
					Point last = p.pollLast();
					area[dx][dy] = 1;
					area[last.x][last.y] = 0;
				}
			}
			else {
				end = true;
			}
			
			sec++;
			if (tidx < m && sec == time[tidx]) {
				if(action[tidx] == 'D')
					dir = (dir+1) % 4;
				else
					dir = (dir-1) < 0 ? 3 : dir -1;
				tidx++;
			}
		}
		System.out.println(sec);
	}

}