백준 3190 (뱀)

문제

---

 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

 

 

 

 

 

풀이

---

Deque 메소드를 이용해서 풀었다.

머리와 꼬리의 좌표를 Deque에 넣어주고 지워주는 방식을 사용하였다.

Deque 와 Queue 와 다른점은 앞과 뒤 모두에서 자료를 삭제 추가해줄 수 있는 점이다.

 

뱀의 방향은

dx = { 1, 0, -1, 0 }

dy = { 0, 1, 0, -1 } 으로 선언하여 사용 하였다.

순서대로 동, 남, 서, 북 으로 움직이는 방향이다.

snakeDir = (snakeDir + dir[timeIdx]) % 4;

총 인덱스가 4개이므로 방향을 전환 시켜줄때 현재의 방향에서 해당 값을 더해준뒤 mod 연산을 통해 방향을 지정했다.

 

//벽과 충돌하는 경우
if(nx <= 0 || nx > n || ny <= 0 || ny > n) {
	System.out.println(second + 1);
	break;
}
// 자신의 몸과 부딪히는 경우
if(map[nx][ny] == 2) {
	System.out.println(second + 1);
	break;
}

위의 두가지 경우가 나오면 그때의 시간을 출력한다.

 

if(map[nx][ny] == 1) {
	//사과를 만난경우 꼬리를 남겨두고 머리를 추가한다.
	map[nx][ny] = 2;
	snake.addFirst(new point(nx, ny));
}
else if(map[nx][ny] == 0) {
	//사과를 만나지 않은 경우 꼬리를 제거하고 머리를 추가한다.
	map[nx][ny] = 2;
	snake.addFirst(new point(nx, ny));
			
	point tail = snake.removeLast();
	map[tail.x][tail.y] = 0; 
}

위의 두가지 경우는 사과인지 아닌지를 판단한다.

앞서 사과는 map 에 1로 저장을 해두었다.

 

 

<전체코드>

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

public class Main {	
	static StringBuilder sb = new StringBuilder();
	static class point{
		int x, y;
		
		public point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	static int[][] map;
	static int[] time;
	static int[] dir;
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(bufferedReader.readLine());
		
		map = new int[n + 1][n + 1];
		
		int number_Apple = Integer.parseInt(bufferedReader.readLine());
		
		for(int i = 0 ; i < number_Apple ; i++) {
			StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
			int y = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			
			map[y][x] = 1;
		}
		
		int L = Integer.parseInt(bufferedReader.readLine());
		dir = new int[L];
		time = new int[L];
		
		for(int i = 0 ; i < L ; i++) {
			StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
			
			time[i] = Integer.parseInt(st.nextToken());
			dir[i] = st.nextToken().equals("D") ? 1 : 3;
		}
		
		int timeIdx = 0;
		int second = 0;
		int snakeDir = 1;
		map[1][1] = 2;
		Deque<point> snake = new ArrayDeque<point>();
		snake.add(new point(1, 1));
		
		while(true) {
			if(timeIdx < L && time[timeIdx] == second) {
				snakeDir = (snakeDir + dir[timeIdx]) % 4;
				timeIdx++;
			}
			
			int nx = snake.getFirst().x + dx[snakeDir];
			int ny = snake.getFirst().y + dy[snakeDir];
			
			if(nx <= 0 || nx > n || ny <= 0 || ny > n) {
				System.out.println(second + 1);
				break;
			}
			if(map[nx][ny] == 2) {
				System.out.println(second + 1);
				break;
			}
			
			if(map[nx][ny] == 1) {
				map[nx][ny] = 2;
				snake.addFirst(new point(nx, ny));
			}
			else if(map[nx][ny] == 0) {
				map[nx][ny] = 2;
				snake.addFirst(new point(nx, ny));
				
				point tail = snake.removeLast();
				map[tail.x][tail.y] = 0; 
			}
			
			second++;			
		}
	}
}