백준 3190 : 뱀

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

3190번: 뱀

[ 문제풀이 ]

전형적인 시뮬레이션 문제이다. 문제의 조건을 잘 읽어보면 결국 가장 중요한 것은 뱀의 머리와 꼬리를 어떻게 관리할 것인가?이다.

N이 최대 100이기 때문에 뱀의 길이는 최대 100 x 100의 길이밖에 될 수 없다. 결국 시간 또한 100 x 100을 넘길 수가 없다. 이후부터는 자신의 몸에 부딪힐 수밖에 없기 때문이다.

​따라서 시간별로 뱀의 몸통 위치와 머리 부분, 꼬리 부분의 좌표를 관리해주면 쉽게 해결할 수 있다.

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;

	static int N, K, L;
	static int snakeHeadY, snakeHeadX, tailIdx, direct;
	static int[] snakeY, snakeX; //시간별로 뱀의 몸통 위치를 저장
	static int[] cmd; //시간별로 명령을 저장
	static int[][] map;

	static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

	public static void main(String[] args) throws IOException {
		N = Integer.parseInt(br.readLine());
		K = Integer.parseInt(br.readLine());

		map = new int[N+1][N+1];
		for (int i = 0; i < K; ++i) {
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());

			map[y][x] = 1;
		}

		snakeY = new int[10010];
		snakeX = new int[10010];
		cmd = new int[10010];

		snakeHeadY = 1; snakeHeadX = 1;
		snakeY[0] = 1; snakeX[0] = 1;
		map[snakeHeadY][snakeHeadX] = 2;

		L = Integer.parseInt(br.readLine());
		for (int i = 0; i < L; ++i) {
			st = new StringTokenizer(br.readLine());
			int t = Integer.parseInt(st.nextToken());
			char c = st.nextToken().charAt(0);

			cmd[t] = c == 'D' ? 1 : 3;
		}

		simulation(1);

		bw.flush();bw.close();br.close();
	}

	public static void simulation(int time) throws IOException {
		//뱀의 머리를 한칸 이동
		snakeHeadY += dir[direct][0];
		snakeHeadX += dir[direct][1];
		
		//범위를 벗어나거나 자신을 만나면 종료
		if (snakeHeadY < 1 || snakeHeadX < 1 || snakeHeadY > N || snakeHeadX > N
				|| map[snakeHeadY][snakeHeadX] == 2) {
			bw.write(time + "\n");
			return;
		}
		
		//현재 시간의 뱀의 위치를 저장
		snakeY[time] = snakeHeadY;
		snakeX[time] = snakeHeadX;

		//움직인 칸에 사과가 없으면 꼬리를 한 칸 줄임
		if (map[snakeHeadY][snakeHeadX] != 1) {
			map[snakeY[tailIdx]][snakeX[tailIdx]] = 0;
			tailIdx++;
		} 

		//map에 뱀 표시
		map[snakeHeadY][snakeHeadX] = 2;

		//방향 전환
		if (cmd[time] != 0) {
			direct = (direct + cmd[time]) % 4;
		}
		
		simulation(time + 1);
	}
}