[PS] 백준 3190번 뱀

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

n X n 보드판위에서 뱀이 0행0열에서 오른쪽 방향으로 출발한다. 처음 몸 길이는 1이고 1초 뒤 현재 머리가 향하고 있는 방향으로 이동한다. 이동한 칸에 사과가 있다면 꼬리는 줄어들지 않는다. 빈 칸이이라면 꼬리가 한 칸 만큼 줄어든다(꼬리의 마지막칸). 그리고 X초에 왼쪽또는 오른쪽으로 머리를 90도만큼 회전한다. 마지막으로, 뱀의 머리가 보드판 밖으로 나가거나 몸과 부딪히면 게임이 끝나게 된다. 이 때, 몇 초에 게임이 종료되는 지를 구하는 문제이다.

grid 상에서 dy, dx 배열을 이용해서 뱀의 이동을 기본 구현하고, x초에 머리를 회전하므로 x초에 어느방향으로 회전해야 하는지를 배열에 담아 기본 구현에 적용한다. 마지막으로, 몸이 이동해온 칸에 남는 것을 구현해야 하는데, 머리가 지나온 칸을 기준으로, 몸의 마지막 칸을 빈 칸으로 만들면 된다. 그리고 머리가 이동한 칸을 몸통으로 만들면 된다. 앞을 없애고, 뒤에 추가하는 큐 자료구조가 이를 구현하기에 적당하겠다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	
	static class Pair {
		int row;
		int col;
		public Pair(int row, int col) {
			this.row = row;
			this.col = col;
		}
	}
	
	int n, k, L, curDir;
	int grid[][];
	int dirs[];
	int dy[] = { 0, 1, 0, -1 };
	int dx[] = { 1, 0, -1, 0 };
	Queue<Pair> q;

	public static void main(String[] args) throws IOException {
		Main ps = new Main();	
		
		ps.solution();
	}

	void solution() throws IOException {
		n = Integer.parseInt(br.readLine());
		k = Integer.parseInt(br.readLine());
		q = new ArrayDeque<>();
		
		grid = new int[n][n]; // 빈칸 := 0, 사과 := 1 몸 := 2
		dirs = new int[10001];
		
		for (int i = 0; i < k; i++) {
			st = new StringTokenizer(br.readLine());
			int row = Integer.parseInt(st.nextToken()) - 1;
			int col = Integer.parseInt(st.nextToken()) - 1;
			
			grid[row][col] = 1;
		}
		
		L = Integer.parseInt(br.readLine());
		
		for (int i = 0; i < L; i++) {
			st = new StringTokenizer(br.readLine());
			int sec = Integer.parseInt(st.nextToken());
			int dir = st.nextToken().charAt(0) == 'L' ? -1 : 1;
			
			dirs[sec] = dir;
		}
		
		q.add(new Pair(0, 0));
		go(0, 0, 0);
	}
	
	void go(int sec, int row, int col) {
		curDir = (curDir + 4 + dirs[sec]) % 4;
		int nRow = row + dy[curDir];
		int nCol = col + dx[curDir];
		
		if (!inRange(nRow, nCol) || grid[nRow][nCol] == 2) {
			// 다음 칸에 갔을 때 종료되므로 현재 초 + 1
			System.out.println(sec + 1);
			return;
		}
		else if (grid[nRow][nCol] == 0) {
			grid[nRow][nCol] = 2;
			q.add(new Pair(nRow, nCol));
			Pair p = q.remove();
			grid[p.row][p.col] = 0;
			go(sec + 1, nRow, nCol);
		} else if (grid[nRow][nCol] == 1) {
			grid[nRow][nCol] = 2;
			q.add(new Pair(nRow, nCol));
			go(sec + 1, nRow, nCol);
		}
		
	}
	
	boolean inRange(int row, int col) {
		return 0 <= row && row < n && 0 <= col && col < n;
	}
}