[문제] 백준 3190번 뱀

www.acmicpc.net/problem/3190

3190번: 뱀

 

내 풀이

구현 문제

public class BOJ_3190 {
	static int[] dx = {0,1,0,-1};
	static int[] dy = {1,0,-1,0};
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());	// 보드 크기
		int K = Integer.parseInt(in.readLine());	// 사과 개수
		
		int[][] matrix = new int[N+1][N+1]; 	// 1 based
		// 사과 위치 
		for(int i=0;i<K;i++) {
			StringTokenizer st = new StringTokenizer(in.readLine()," ");
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			matrix[r][c] = 1;
		}
		
		int L = Integer.parseInt(in.readLine());	// 방향 변환 횟수
		// 아래처럼 안하고 냥 char[] dirch = new char[10001];해서 시간을 인덱스로 쓸 수 있음
		int[] when = new int[L]; char[] dirch = new char[L];	
		// 방향전환 입력받기
		for(int i=0;i<L;i++) {
			StringTokenizer st = new StringTokenizer(in.readLine(), " ");
			when[i]= Integer.parseInt(st.nextToken());
			dirch[i] = st.nextToken().charAt(0);
		}
		
		int dir = 0, index=0, time = 0;	// 초기 길이, 방향(오른쪽), 방향전환배열의 인덱스, 총 소요시간
		int[] head = new int[] {1,1};	// 머리 위치
		Queue<int[]> q = new LinkedList<>();	// 뱀이 있는 위치 좌표들
		q.offer(head);
		
		while(true) {
			// 사과 위치
			time++;
			// 머리 앞으로 이동
			head[0] += dx[dir];
			head[1] += dy[dir];
			
			// 영역 벗어나면 중지
			if(head[0]<1 || head[0]>N || head[1]<1 || head[1]>N) {
				break;
			}
			// 자기 몸이랑 닿으면 중지
			else if(matrix[head[0]][head[1]]==2){
				break;
			}
			// 사과 있는 칸이면,
			else if(matrix[head[0]][head[1]]==1){
				matrix[head[0]][head[1]] = 0;	// 사과 먹음 -> 0
			}
			// 빈칸이면 꼬리한칸 이동
			else {
				int[] tail = q.poll();	// 가장 마지막에
				matrix[tail[0]][tail[1]] = 0;
			}
			
			q.offer(new int[] {head[0], head[1]});	// 뱀의 위치 큐에 저장
			matrix[head[0]][head[1]] = 2;	// 뱀 위치 표시
			
			// 방향전환
			if(index<L) {
				if(when[index] == time) {
					if(dirch[index]=='D') dir = (dir+1)%4;
					else if(dirch[index]=='L') dir = (dir+3) %4;
					index++;
				}
			}
		}
		System.out.println(time);
	}
}