백준/3190/Java - 뱀

문제

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

3190번: 뱀

---

 뱀이 움직이면서 사과를 만나면 길이가 길어지는 게임. 단 뱀의 머리가 자신의 몸통이나 벽에 부딪히면 게임이 종료된다.

 

1. NxN 보드 위에서 게임이 진행되기 때문에 이차원 배열이 필요할 것이다.

2. 배열에 사과가 있는 지 표시해야 하므로 boolean 타입 배열을 사용해야겠다고 생각했다. 하지만 사과뿐만 아니라 뱀이 해당 칸위에 올라와 있는 지도 표시해야 하므로 int 타입으로 나타냈다. (빈칸, 사과, 뱀으로 구분)

3. L과 D. n초가 되면 우측이나 좌측으로 이동방향이 바뀐다. 뱀이 상하좌우 어느 곳을 보고 있느냐에 따라서 다음 방향이 달라지게 된다.

    이를 조건을 나누어 처리했다.

4. 뱀은 1초에 한칸씩 계속 움직인다. 따라서 1초마다 방향에 따라서 x,y좌표가 각각 1이 증가하거나 1이 감소한다. 뱀의 머리 방향에 따라 달라지는 x, y 좌표 변화량을 배열로 나타냈다.

5. 5 D, 8 D가 연속으로 주어질 경우, 5초 이동하고 방향이 오른쪽으로, 그리고 3초 뒤인 8초에 또 다시 방향이 오른쪽으로 바뀌는 것이다.

     5초 뒤에 바뀌고, 8초 뒤에 바뀌는 것이 아니다.(문제를 대충 읽고 바보같이 이해해서 이것 때문에 한참을 해맸다...ㅠㅠ)

     따라서 뱀의 방향 변환 정보가 주어지면 정보 1개마다 처리하는 것이 아니라, 몇초에 어떻게 변환해야 하는지 저장(Key - Value)해놓고       활용해야 한다.

6. 머리가 추가 될 때는 앞에, 꼬리를 지울 때는 뒤에서부터 지워야하므로 Deque 자료형을 활용한다.

 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
	
	//보드의 크기, 사과의 개수, 뱀의 방향변환 횟수. 
	static int N,K,L;
	//보드
	static int[][] board; // 0 : 비어있음 , 1 : 사과 , 2: 뱀이 위에 있음. 
	//초 
	static int sec = 0;
	//머리가 향하고 있는 방향.  0 1 2 3 상 하 좌 우.
	static int dir;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	//언제 방향이 바뀌는지 저장.
	static HashMap<Integer, String> moving = new HashMap<>();
	//뱀
	static Deque<Snake> snake = new ArrayDeque<>();

	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		board = new int[N][N];
		K = Integer.parseInt(br.readLine());
		//뱀의 시작 지점. 0,0 
		snake.addFirst(new Snake(0, 0));
		board[0][0] = 2;
		dir = 3; //시작할 때는 머리가 우측을 보고 있음. 
		//사과 위치 표시. 
		for(int i=0; i<K; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int x = Integer.parseInt(st.nextToken()) - 1; // 문제에선 시작점이 1,1이지만 코딩 편의상 0,0에서 시작하므로 사과의 좌표도 1씩 빼준다. 
			int y = Integer.parseInt(st.nextToken()) - 1;
			
			board[x][y] = 1;
		}
		//명령어 개수. 
		L = Integer.parseInt(br.readLine());
		int s;//이동하는 초.  
		String d;//방향 
		for(int i=0; i<L; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			s = Integer.parseInt(st.nextToken());
			d = st.nextToken();
			moving.put(s, d);
		}
		move();
		sb.append(sec);
		System.out.println(sb);
	}
	//뱀의 움직임. 
	static void move() {
		while(true) {
			sec++;
			Snake cur = snake.peekFirst();
			Snake next = new Snake(cur.x + dx[dir], cur.y + dy[dir]);

			//벽에 부딪히거나 몸통에 닿으면 종료. 
			if(next.x < 0 || next.y < 0 || next.x >= N || next.y >= N || board[next.x][next.y] == 2) break;
			
	
			//사과를 먹었는지 안먹었는지 검사 
			if(board[next.x][next.y] == 1) {//사과를 먹었다면 추가만 하면 됨.
				snake.addFirst(next);
				board[next.x][next.y] = 2;
			} else {//사과를 안먹었다면 추가하고 꼬리 자름.
				snake.addFirst(next);
				board[next.x][next.y] = 2;
				Snake tail = snake.pollLast();
				board[tail.x][tail.y] = 0;
			}
			
			if(moving.containsKey(sec)) {
				String d = moving.get(sec);
				//방향이 바뀌는 초에는 d에 따라 다음 방향이 결정됨.
				if(dir == 0) { //상
					if(d.equals("L")) dir = 2;
					else dir = 3;
				}
				else if(dir == 1) {//하 
					if(d.equals("L")) dir = 3;
					else dir = 2;
				}
				else if (dir == 2) { //좌 
					if(d.equals("L")) dir = 1;
					else dir = 0;
				}
				else { //우 
					if(d.equals("L")) dir = 0;
					else dir = 1;
				}
			}
		}
		
	}

	//뱀의 위치 저장. 
	static class Snake {
		int x;
		int y;
		Snake(int x, int y){
			this.x = x;
			this.y = y;
		}
		
	}
		
}