[백준] 3190 - 뱀

[문제링크]

3190번: 뱀

 

0. 스네이크 게임에서 생존 시간을 구하는 문제

 

1. 초기 방향은 항상 오른쪽이므로, 주어지는 방향 전환 데이터를 통해 몇초에, 어떤 방향으로 변하는지 미리 저장한다

 

2. 머리가 진행할 때, 해당 지점에 이동 방향 정보를 저장해 두어, 꼬리가 당겨질 때의 방향을 알 수 있도록 한다

 

3. 매 초 머리를 향하는 방향으로 이동하며,

• 사과가 나온다면 - 길이를 1 늘린다, 즉 꼬리의 길이를 줄이지 않는다
• 빈 공간이라면 - 꼬리를 이동시킨다
• 벽이라면 - 종료한다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
	
	static int[][] d={
		{0,0}, {0,-1}, {-1,0}, {0,1}, {1,0}
	};
	static int[][]map;
	static int[][]move;
	static int N;
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = pint(br.readLine());
		
		map=new int[N+2][N+2];
		for (int i = 0; i < N+2; i++) {
			map[0][i]=-1;
			map[N+1][i]=-1;
			map[i][0]=-1;
			map[i][N+1]=-1;
		}
		
		int k = pint(br.readLine());
		
		for (int i = 0; i < k; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			map[ pint(st.nextToken()) ][ pint(st.nextToken()) ]=5; // 사과 위치 표시
			
		}
		int L = pint(br.readLine());
		move = new int[L][2]; // 몇초에, 어떤 방향으로 바꿀지 저장
		int dir = 3; // 초기 방향
		for (int i = 0; i < L; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			move[i][0]=pint(st.nextToken());
			//현재 방향을 보고 다음 방향 계산
			switch (st.nextToken()) {
			case "D":
				dir++;
				if(dir==5)dir=1;
				move[i][1]=dir;
				break;
			case "L":
				dir--;
				if(dir==0)dir=4;
				move[i][1]=dir;
				break;
			default:
				break;
			}
		}
		
		int time=0; //생존 시간(구하려는 답)
		int cnt=0; // 회전 횟수
		dir=3;//초기방향
		int headX=1, headY=1;
		int tailX=1, tailY=1;
		while(true) {
			time++;
			//head이동
			map[headX][headY]=dir;
			headX+=d[dir][0];
			headY+=d[dir][1];

			if(map[headX][headY]==5) {//사과면 꼬리가 한칸 늘어나는효과 = 꼬리를 줄이지 않는다
			}
			else if(map[headX][headY]!=0) {//벽이면 죽음
				break;
			}
			else {//빈칸이면 꼬리를 한칸 당긴다
				int temp = map[tailX][tailY];
				map[tailX][tailY]=0;
				tailX+=d[temp][0];
				tailY+=d[temp][1];
			}
			
			//회전
			if(cnt<L && time == move[cnt][0]) {
				dir=move[cnt][1];
				cnt++;
			}
		}
		System.out.println(time);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면