[백준 3190번] 뱀

www.acmicpc.net/problem/3190

3190번: 뱀

 

문제는 이해했지만 어떻게 구현할지 굉장히 막막했던 문제였습니다. 

주어지는 입력 자체도 굉장히 까다로웠습니다. 경과된 시간을 주고 그 때 방향이 주어지는데 어떻게 구현하고 이 입력을 해석 해야 하는지 감이 잡히지 않았습니다.

 

풀이를 참고해보니, 데큐를 이용해서 뱀을 구현했더군요. 

!!! 굉장히 편리한 방식이었습니다. 

 

경과된 시간이 주어지는 입력에 대한 접근 방식에도 꽤 도움이 됐던 문제였습니다.

 

...

/*
백준 3190번 - 뱀
https://www.acmicpc.net/problem/3190
 */
public class Main {
	static int n,k,l;
	static int[][] apple;
	static boolean[][] visited;

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		BufferedReader br = new BufferedReader(new FileReader("testcase.txt"));
		n = Integer.parseInt(br.readLine());
		k = Integer.parseInt(br.readLine());

		apple = new int[n][n];

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

		l = Integer.parseInt(br.readLine());
		Queue<Command> commandQueue = new ArrayDeque<>();
		for (int i = 0; i < l; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			commandQueue.add(new Command(Integer.parseInt(st.nextToken()), st.nextToken().charAt(0)));
		}

		visited = new boolean[n][n];
		int[][] directions = {{0,1}, {1,0}, {0,-1}, {-1,0}}; //동 남 서 북
		int time = 0;
		int directionIdx = 0;
		ArrayDeque<Location> snake = new ArrayDeque<>();
		snake.add(new Location(0,0));
		visited[0][0] = true;

		while(true) {
			time++;
			Location before = snake.peekLast();
			Location current = new Location(before.y + directions[directionIdx][0], before.x+directions[directionIdx][1]);
			//범위를 벗어나거나 몸에 부딪히는 경우
			if(!current.isRange(n) || visited[current.y][current.x]) {
				System.out.println(time);
				break;
			}

			visited[current.y][current.x] = true;
			snake.add(current);

			//사과가 있는 자리인 경우
			if(apple[current.y][current.x] == 1) apple[current.y][current.x] = 0; // 사과 먹음
			//사과가 없는 자리인 경우
			else {
				Location tail = snake.pollFirst();
				visited[tail.y][tail.x] = false;
			}

			//방향 전환
			if(!commandQueue.isEmpty() && commandQueue.peek().time == time) {
				if (commandQueue.peek().turn == 'L') {
					directionIdx = (directionIdx + 3) % 4;
				}else
					directionIdx = (directionIdx + 1) % 4;
				commandQueue.poll();
			}
		}
	}
}
class Location {
	int x,y;

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

	public boolean isRange(int n) {
		if(x < 0 || x >= n || y < 0 || y >= n) return false;
		return true;
	}

}

class Command{
	int time;
	char turn;

	public Command(int time, char turn) {
		this.time = time;
		this.turn = turn;
	}
}