[백준] 3190 뱀 / 자바(Java)

문제

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

3190번: 뱀

 

---

해설

2차원 배열에서의 구현을 4방탐색을 통해 해결하는 문제입니다.

조건들을 주의해서 확인해야합니다. 

 

뱀의 회전 시간 및 여부는 입력이 정렬된 상태로 주어져 올바른 시간에 맞추어 진행하다 한번씩 꺽어주면 됩니다.

새로 진행할 부분의 위치를 head배열에 저장하고 진행시 사과가 없어 꼬리가 당겨져 몸이 지워질 부분을 tail배열에 저장합니다. 

 

head의 값은 회전 및 전진하며 자신이나 벽과 닿은 경우 바로 종료하도록 break하고, 이동 가능한 경우 해당 위치에 몸이 있음을 지도에 저장합니다. 여기서 사과가 없는 경우는 tail이 줄어들어야 하므로 꼬리측의 몸을 지도에서 지우고 head와 마찬가지로 이동합니다.

 

꼬리가 따라가게 하는 방식이 까다롭지만 머리의 이동 시간과 꼬리의 이동 시간은 뱀의 길이만큼 차이가 난다는 점을 확인하면 조건에 맞추어 해결가능합니다.

주의점

• 회전시 이전에 움직이던 방향을 기준으로 왼쪽이나 오른쪽이 정해진다
• 머리가 먼저 움직이고 이후 꼬리가 움직인다.
• 자신의 몸에 닿아도 죽기 때문에 꼬리의 위치를 파악해야 한다. -> 꼬리의 방향 회전을 알기 위해 현 시간에서 길이를 빼면 꼬리가 꺽일 시간을 알 수 있다.

---

코드

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

public class Main{

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int K = Integer.parseInt(br.readLine());
		
		int apples [][] = new int [K][2];
		for(int i=0;i<K;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			apples[i][0] = Integer.parseInt(st.nextToken());
			apples[i][1] = Integer.parseInt(st.nextToken());
		}
		
		int L = Integer.parseInt(br.readLine());
		int snake1 [] = new int [L];
		char snake2 [] = new char [L];
		for(int i=0;i<L;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			snake1[i] = Integer.parseInt(st.nextToken());
			snake2[i] = st.nextToken().charAt(0);
		}
		
		int board[][] = new int [N+1][N+1];
		board[1][1] = 1;
		for(int i=0;i<K;i++) {
			board[apples[i][0]][apples[i][1]]=2;
		}
		
		int time=0;
		int snakeidx=0;
		int tailidx = 0;
		int length = 0;
		//우 하 좌 상
		int dr[] = {0,1,0,-1};
		int dc[] = {1,0,-1,0};
		int head[] = {1,1};
		int tail[] = {1,1};
		int dirctionidx = 0;
		int taildirctionidx = 0;
		while(true) {
			
			
			// 미리 입력된 방향변경 시간이 된 경우 
			if(snakeidx<L && time==snake1[snakeidx]) {
				//방향전환
				dirctionidx=changedirction(snake2[snakeidx], dirctionidx);
				snakeidx++;
			}
			
			//1보 전진
			//머리이동(불가능하다면 break;)
			int newr = head[0]+dr[dirctionidx];
			int newc = head[1]+dc[dirctionidx];
			// 벽 또는 자신과 부딪힌 경우-> 바로 종료
			if(newr<=0 || newc<=0 || newr>N || newc>N || board[newr][newc]==1) {
				time++;
				break;
			}
			// 사과가 없으면 -> 꼬리를 당겨야 함
			if(board[newr][newc]==0) {
				int tailtime = time-length;
				if(tailidx<L&&tailtime == snake1[tailidx]) {
					taildirctionidx=changedirction(snake2[tailidx], taildirctionidx);
					tailidx++;
				}
				int newtailr = tail[0]+dr[taildirctionidx];
				int newtailc = tail[1]+dc[taildirctionidx];
				board[tail[0]][tail[1]]=0;
				tail[0]=newtailr;
				tail[1]=newtailc;
			}else {// 사과를 먹은 경우
				//꼬리는 그대로, 길이 증가
				length++;
			}
			
			// 머리는 항상 동일하게 이동
			board[newr][newc]=1;
			head[0] = newr;
			head[1] = newc;
			time++;

			//System.out.println(time);
			//for(int i=0;i<N+1;i++) {
			//	System.out.println(Arrays.toString(board[i]));
			//}
			//System.out.println();
		}
		System.out.println(time);
	}
	
	static int changedirction(char chr, int dirction) {
		//우 하 좌 상
		switch (dirction) {
		case 0: // 이전 방향이 우 인경우
			if(chr=='L') { 
				return 3;
			}else {
				return 1;
			}
		case 1: // 이전 방향이 하 인경우
			if(chr=='L') { 
				return 0;
			}else {
				return 2;
			}
		case 2: // 이전 방향이 좌 인경우
			if(chr=='L') { 
				return 1;
			}else {
				return 3;
			}
		case 3: // 이전 방향이 상 인경우
			if(chr=='L') { 
				return 2;
			}else {
				return 0;
			}

		}
		return -1;
	}
}