[알고리즘] 백준-3190 뱀

만약, deque에 대한 것을 알고 싶으시다면 아래 URL을 확인해주세요 😉
https://velog.io/@esun1903/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Deque

✨ 문제에 적용해보기

백준 - 뱀이라는 문제에 deque를 적용해보아요 😉

3190번: 뱀

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	public static int N, L, K;
	public static int time = 0;

	public static Deque<Snake> deque = new LinkedList<>();
	public static Deque<Dir> direction = new LinkedList<>();

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = Integer.parseInt(br.readLine());
		int board[][] = new int[N + 1][N + 1];

		K = Integer.parseInt(br.readLine());
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			board[r-1][c-1] = 2; // 사과의 위치
		}

		L = Integer.parseInt(br.readLine());
		// 뱀의 방향 변환 정보
		for (int i = 0; i < L; i++) {
			st = new StringTokenizer(br.readLine());
			int time = Integer.parseInt(st.nextToken());
			String dir = st.nextToken();
			direction.add(new Dir(time, dir.charAt(0)));
		}

		gameStart(direction, board);
		System.out.println(time);

	}// end of main

	private static void gameStart(Queue<Dir> direction, int[][] board) {
		deque.addFirst(new Snake(0, 0, 1));
		board[0][0] = 1;

		// 머리 방향대로 기어가야함
		while (true) {
			Snake snake = deque.getFirst();
 
			int r = snake.r;
			int c = snake.c;
			int dir = snake.dir;
			// 1,1꺼냈어
			if (dir == 1) { // 방향이 오른쪽일때,
				c += 1;
			} else if (dir == 2) { // 2이면 위쪽
				r -= 1;
			} else if (dir == 3) { // 3이면 왼쪽
				c -= 1;
			} else if (dir == 4) { // 4이면 아래쪽
				r += 1;
			}
			time++;
			if (wallChecking(r, c) == true && board[r][c] != 1) {
				// 사과가 없을 때,
				if (board[r][c] != 2) {
					Snake tail = deque.pollLast();
					board[tail.r][tail.c] = 0;
				}

				deque.addFirst(new Snake(r, c, dir));
				dirChecking(time);
				board[r][c] = 1;
			} else {
				break;
			}

		}

	}// end of gameStart

	private static void dirChecking(int time) {

		if(direction.size()>0) {
		Dir d = direction.peekFirst();
		if (time == d.time) {
			Snake s = deque.getFirst();
			if (d.dir == 'L') {
				if (s.dir != 4) {
					s.dir += 1;
				} else {
					s.dir = 1;
				}
			} else {
				if (s.dir != 1) {
					s.dir -= 1;
				} else {
					s.dir = 4;
				}
			}
			direction.pollFirst();
		} 
		}
		

	}// end of method

	private static boolean wallChecking(int r, int c) {
		if (r < N && 0 <= r && c < N && 0 <= c) {
			return true;
		}
		return false;
	}

	public static class Dir {
		int time;
		char dir;

		public Dir(int time, char dir) {
			super();
			this.time = time;
			this.dir = dir;
		}
	}

	public static class Snake {
		int r;
		int c;
		int dir;

		// 만약, dir이 1이면 오른쪽, 2이면 위쪽, 3이면 왼쪽, 4이면 아래쪽
		public Snake(int r, int c, int dir) {
			super();
			this.r = r;
			this.c = c;
			this.dir = dir;
		}
	}// end of
}// end of class

뱀이라는 문제는 뱀의 머리 위치와 꼬리 위치를 가변적으로 변경해야하는 문제이기 때문에 덱을 활용하면 좀 더 쉽게 구현할 수 있습니다.

뱀의 머리 위치는 계속 덱에 위치들을 넣고, (deque.add(new Snake ~ 부분입니다.)

사과가 없는 경우, pollLast() 함수를 사용하여 뱀의 꼬리 위치를 지우는 점이 핵심이라고 할 수 있습니다 😉