[BOJ] 3190. 뱀

문제

BOJ 3190. 뱀

풀이

덱을 이용해서 풀 수 있는 시뮬레이션 문제.
뱀의 몸의 좌표를 담아주는 Deque<.Point>
사과의 위치(1)와 뱀의 몸(2), 빈 공간(0)을 담는 int[][] map
방향 전환을 담아주는 char[] change를 사용했다.

뱀의 머리 좌표에 di[dir],dj[dir]을 더해주고 map의 범위를 벗어나지 않는다면 deque에 추가해 주었다.
이 추가한 좌표를 기준으로 이동한 칸에 사과가 존재하는 경우, 빈 공간인 경우, 뱀의 몸인 경우로 나누어서 처리해주었다.
그리고 마지막에 change[time]에 'L'또는 'D'가 담겨있으면 뱀의 방향 변환을 해줘야 한다는 의미이기 때문에 해당 방향에 따라 dir을 변경해 주었다.
while문을 반복하다가 뱀의 머리가 map의 범위를 벗어나거나 뱀의 몸을 만나면 게임 진행 시간을 리턴했다.

JAVA코드

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

public class 백준3190_뱀 {
	static int[][] map; // 1: 사과가 위치, 2: 뱀의 몸
	static int N, K, L; // 보드의 크기, 사과의 개수
	static char[] change = new char[10001]; // 방향 전환을 담을 배열

	static class Point {
		int x, y;

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

	static int[] di = { 0, 1, 0, -1 }; // 우,하,좌,상
	static int[] dj = { 1, 0, -1, 0 };

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		K = Integer.parseInt(br.readLine());

		map = new int[N + 1][N + 1];
		StringTokenizer st;
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			map[x][y] = 1;
		}

		L = Integer.parseInt(br.readLine());
		for (int i = 0; i < L; i++) {
			st = new StringTokenizer(br.readLine());
			int time = Integer.parseInt(st.nextToken());
			char dir = st.nextToken().charAt(0);
			change[time] = dir;
		}

		int ans = dummy();
		System.out.println(ans);

	}

	public static int dummy() {
		Deque<Point> deque = new ArrayDeque<>(); // 뱀의 몸의 좌표 저장
		deque.add(new Point(1, 1));
		map[1][1] = 2;
		int time = 0;
		int dir = 0;

		Point head = deque.getFirst();
		while (true) {

			time++;

			int nexti = head.x + di[dir];
			int nextj = head.y + dj[dir];

			if (nexti < 1 || nextj < 1 || nexti > N || nextj > N)
				return time;

			deque.addFirst(new Point(nexti, nextj));

			head = deque.getFirst();


				if (map[head.x][head.y] == 1) {	//사과가 있는 경우
					map[head.x][head.y] = 2;
				} else if (map[head.x][head.y] == 0) {	// 사과가 없는 경우
					Point point = deque.pollLast();
					map[point.x][point.y] = 0;
					map[head.x][head.y] = 2;
				} else if (map[head.x][head.y] == 2) {	// 내 몸이네? 그럼 게임 종료
					return time;
				}


			// 방향을 바꿀 시간인지
			char ch = change[time];
			if (ch == 'L') {
				dir = ((dir + 3) % 4);
			} else if (ch == 'D') {
				dir = (dir + 1) % 4;
			}

		}

	}
}