[삼성기출]백준3190 - 뱀

package sw;

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

public class Main{
	
	static int N,K,L;
	static int t;
	static int[][] map, dir = {{0,1},{1,0},{0,-1},{-1,0}};
	static boolean check(int x, int y) {
		if(x>=0 && x<map.length && y>=0 && y<map[x].length) {
			return true;
		}else return false;
	}
	
	static int direction;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine().trim());
		K = Integer.parseInt(br.readLine().trim());

		map = new int[N][N]; // 뱀:1, 사과:2	
		
		String[] input;
		int x,y;
		for(int i=0; i<K; i++) {
			input = br.readLine().trim().split(" ");
			x = Integer.parseInt(input[0]) - 1;
			y = Integer.parseInt(input[1]) - 1;
			map[x][y] = 2;
		}

		t = 0;
		
		List<Pos> snake = new LinkedList<>();
		map[0][0] = 1;
		snake.add(new Pos(0,0));
		direction = 0;

		L = Integer.parseInt(br.readLine().trim());
		int X; 	// 이동횟수
		char C; // L 왼, R
		int dx,dy;
		Pos tmp;
		
		for(int i=0; i<L; i++) {
			input = br.readLine().trim().split(" ");
			X = Integer.parseInt(input[0]);
			C = input[1].charAt(0);
			dx = snake.get(0).x + dir[direction][0];
			dy = snake.get(0).y + dir[direction][1];
			while(X>t || i == (L-1)) {	// 마지막에는 계속 돌려.
				if(!check(dx,dy)) {
					System.out.println(t+1);
					return;
				}
				if(map[dx][dy] == 0) {
					snake.add(0, new Pos(dx,dy));
					tmp = snake.get(snake.size()-1);
					snake.remove(snake.size()-1);
					map[dx][dy] = 1;
					map[tmp.x][tmp.y] = 0; 
				}else if(map[dx][dy] == 1){
					System.out.println(t+1);
					return;
				}else if(map[dx][dy] == 2){
					snake.add(0, new Pos(dx,dy));
					map[dx][dy]=1;
				}
				t++;
				if(t==X && i ==(L-1)) direct(C);	// 마지막에 머리 꺾어주고 계속 돌리기 
				dx = snake.get(0).x + dir[direction][0];
				dy = snake.get(0).y + dir[direction][1];
			}
			direct(C);
		}
		
		
	}
	
	static void direct(char c) {
		if(c == 'D') {
			direction = (direction+1)%4;
		}else if(c == 'L') {
			direction = (direction+3)%4;
		}
	}
	
	static class Pos{
		int x,y;

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

		@Override
		public String toString() {
			return "[" + x + "," + y + "]";
		}
		
	}
}