백준 3190 - 뱀

Java

3190 번 - 뱀

문제

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

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

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

먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다. 사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

접근 방법

while문을 통해 한 번 반복할 때 마다 1초씩 증가하게 하였다.
뱀의 상태는 Queue를 이용해서 나타내었다.
뱀이 이동할 때 마다, 이동한 칸의 위치를 queue에 add하고, 만약 이동한 칸에 사과가 없으면 poll을 하여 꼬리를 제거해 준다.

코드

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

public class Main {
	static int n, appleN, orderN, time;
	static int[][] map;
	static int[] orderT;
	static char[] order;
	// 우, 하, 좌, 상
	static int[] dy = {0,1,0,-1};
	static int[] dx = {1,0,-1,0};	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());
    	map = new int[n][n];
    	appleN = stoi(br.readLine());
    	for(int i = 0; i < appleN; i++) {
    		stk = new StringTokenizer(br.readLine());
    		map[stoi(stk.nextToken()) - 1][stoi(stk.nextToken()) - 1] = 2;	// apple
    	}
    	orderN = stoi(br.readLine());
    	order = new char[orderN];
    	orderT = new int[orderN];
    	for(int i = 0; i < orderN; i++) {
    		stk = new StringTokenizer(br.readLine());
    		orderT[i] = stoi(stk.nextToken());
    		order[i] = stk.nextToken().charAt(0);
    	}
    	int y = 0, x = 0, dir = 0, idx = 0;
    	Queue<Pair> snake = new LinkedList<>();
    	map[y][x] = 1;
    	snake.add(new Pair(y,x));
    	while(true) {
    		time++;
    		// 맵 밖으로 나가거나, 자기 자신을 잡아 먹으면 종료
    		if(y + dy[dir] < 0 || y + dy[dir] == n || x + dx[dir] < 0 || x + dx[dir] == n || map[y + dy[dir]][x + dx[dir]] == 1) {
    			break;
    		}
    		y += dy[dir];	// 이동
    		x += dx[dir];
    		snake.add(new Pair(y,x));	// 뱀 머리 추가
    		if(map[y][x] != 2) {		// 만약 사과를 먹지 않았다면, 꼬리를 자른다
    			Pair tail = snake.poll();
    			map[tail.y][tail.x] = 0;
    		}
    		map[y][x] = 1;
    		if(idx < orderN && orderT[idx] == time) {	// 방향 변경
    			if(order[idx] == 'D') {
    				dir = (dir + 1) % 4;
    			}
    			else {
    				dir = (dir - 1 + 4) % 4;
    			}
    			idx++;
    		}
    	}
    	System.out.println(time);
    	br.close();
	}
	static class Pair{
		int y,x;
		Pair(int y, int x){
			this.y = y;
			this.x = x;
		}
		@Override
		public String toString() {
			StringBuilder builder = new StringBuilder();
			builder.append("[").append(y).append(", ").append(x).append("]");
			return builder.toString();
		}
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

⭐⭐★★★

후기

간단한 구현 문제였다.

개선할 점

없