[BOJ] 3190 뱀

 

 

[문제]

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

 

 

[소스 코드]

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

public class Main {
	static int[] dr = {0,1,0,-1};
	static int[] dc = {1,0,-1,0};
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());
		int k = Integer.parseInt(br.readLine());
		int[][] map = 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());
			map[r][c] = 1; 
		}
		int l = Integer.parseInt(br.readLine());
		HashMap<Integer,String> hm = new HashMap<>();
		for(int i=0;i<l;i++) {
			st = new StringTokenizer(br.readLine());
			int key = Integer.parseInt(st.nextToken());
			String val = st.nextToken();
			hm.put(key, val);
		}
		Deque<int[]> q = new LinkedList<>();
		boolean[][] body = new boolean[n+1][n+1];
		q.offer(new int[] {1,1});
		body[1][1] = true;
		int result = 0;
		int dir = 0;
		while(true) {
			result++;
			int nr = q.peekLast()[0] + dr[dir];
			int nc = q.peekLast()[1] + dc[dir];
			if(nr<1 || nr>n || nc<1 || nc>n || body[nr][nc]) break;
			else {
				if(map[nr][nc]==1) {
					map[nr][nc] = 0;
					q.offer(new int[] {nr,nc});
					body[nr][nc] = true;
				}
				else {
					q.offer(new int[] {nr,nc});
					body[nr][nc] = true;
					int[] tail = q.poll();
					body[tail[0]][tail[1]] = false;
				}
			}
			if(hm.containsKey(result)) {
				String str = hm.get(result);
				if(str.equals("D")) dir = (dir+1) % 4;
				else dir = (dir+3) % 4;
			}
		}
		System.out.println(result);
	}
}