[백준] 3190: 뱀 문제 풀이

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

접근 방식

뱀이 이동하고, 길이가 변화하는 로직을 덱(ArrayDeque)으로 구현해보았다.
뱀이 앞으로 이동하면 덱의 앞부분에 해당 좌표를 입력하고, 뱀이 사과를 먹지 못하면 덱의 뒷부분을 제거(pollLast)한다.
뱀이 이동할 때마다 2차원 배열의 해당 값을 바꿔준다.

또한 시간이 지날 때마다 발생하는 방향 전환 명령어도 덱으로 묶어두었다.
현재 경과한 시간이 덱의 가장 첫번째 명령어의 시간과 일치하면(peek), 덱의 맨 앞부분을 꺼내서(poll) 방향 전환을 한다.

시뮬레이션

1. 매 초마다 snake의 맨 앞부분으로부터 이동할 위치를 확인한다.

int head [] = snake.peek(); // 뱀의 머리 부분의 좌표
int ny = head[0] + dy[d]; // 이동할 좌표
int nx = head[1] + dx[d];

2. 만약 이동 가능하다면 snake의 맨 앞에 이동하려는 부분의 좌표를 추가한다. 만약 이동한 부분에 사과가 없다면 snake의 맨 뒤의 부분을 제거하고, 해당 위치를 0으로 바꿔준다.

if (0<ny&&ny<=N&&0<nx&&nx<=N&&arr[ny][nx]!=1) { // 해당 좌표로 이동 가능하다면
	snake.addFirst(new int [] {ny,nx}); // 뱀의 머리 부분에 해당 좌표 추가
	if (arr[ny][nx] == 0) { // 만약 이동할 부분이 사과가 없다면
		int del[] = snake.pollLast(); // 뱀의 꼬리 부분 제거
		arr[del[0]][del[1]] = 0; // 뱀의 꼬리였던 부분 0으로 변경
	}
	arr[ny][nx] = 1; // 뱀의 머리 부분 1로 변경
} else break; // 해당 좌표가 벽이거나, 뱀의 몸이 위치한 곳이면 종료

만약 이동이 불가능하다면(벽 혹은 뱀의 몸이라면) 반복을 종료한다.

3. 이동이 끝난 후, 현재 시간이 방향전환을 해야할 시간이라면 해당 명령어를 덱에서 꺼내고 방향을 전환한다.

if (!comm.isEmpty() && sec == comm.peek()[0]) { // 현재 커맨드들이 존재하고, 제일 앞 커맨드가 현재 시간과 같다면 
	int key = comm.poll()[1]; // 제일 앞 커맨드를 꺼내어 방향전환 key를 가져온다.
	if (key == 'L') d = (d + 1)%4; // L이면 좌회면
	else d = (d+3)%4; // 그렇지 않다면 우회전
}

1~3 과정이 끝났으면 시간을 증가시킨다.

전체 코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int [][] arr = new int[N+1][N+1];
		int K = Integer.parseInt(br.readLine());
		
		for (int i = 0; i < K; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int row = Integer.parseInt(st.nextToken());
			int col = Integer.parseInt(st.nextToken());
			arr[row][col] = 2;
		}
		
		int L = Integer.parseInt(br.readLine());
		ArrayDeque<int []> comm = new ArrayDeque<>();
		for (int i = 0; i < L; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int X = Integer.parseInt(st.nextToken());
			int C = st.nextToken().charAt(0);
			comm.add(new int[] {X, C});
		}
		
		int [] dy = {0, -1, 0, 1};
		int [] dx = {1, 0, -1, 0};
		
		ArrayDeque<int []> snake = new ArrayDeque<>();
		arr[1][1] = 1;
		snake.add(new int[] {1, 1});
		int d = 0;
		int sec = 1;
		while (true) {
			int head [] = snake.peek();
			int ny = head[0] + dy[d];
			int nx = head[1] + dx[d];
			
			if (0<ny&&ny<=N&&0<nx&&nx<=N&&arr[ny][nx]!=1) {
				snake.addFirst(new int [] {ny,nx});
				if (arr[ny][nx] == 0) {
					int del[] = snake.pollLast();
					arr[del[0]][del[1]] = 0;
				}
				arr[ny][nx] = 1;
			} else break;
			
			if (!comm.isEmpty() && sec == comm.peek()[0]) {
				int key = comm.poll()[1];
				if (key == 'L') d = (d + 1)%4;
				else d = (d+3)%4;
			}
			sec++;
		}
		System.out.println(sec);
	}
}