[backjoon]3190 뱀 (java)

www.acmicpc.net/problem/3190

3190번: 뱀

Gold 5

문제 상황대로 풀이하면 되는 문제.

뱀이 성장한 만큼 이동인지 머리만 한칸씩 이동인지가 헷갈려서 시간이 오래걸렸다.

방향 전환과 문제의 종료 조건만 잘 구분해주면 됨.

방향 전환은 시간을 기록하고 그 시간에 방향을 바꿔주면 된다.

벽을 만나는 경우는 일반적인 bfs처럼 풀이하면 되고(해당 문제가 bfs 풀이는 아님)

뱀이 자신의 몸을 만나는지에 대한 풀이는, 나의 경우엔 뱀의 경로를 전부다 기록하고 뱀의 길이만큼 역추적하는 방식으로 검증하였다. 하지만, 뱀의 길이만큼 리스트를 만들어서 사과를 못 먹으면 꼬리를 뺴주는 방식으로 해서 검증할 대상을 만드는 것도 좋은 방법이다.

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

class Main {
    //동남서북
	static int[][] dir = { {0,1},{1,0},{0, -1},{-1, 0}};
	public static void main(String[] args) throws Exception {
        
        int curDir = 0;
        
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int[][] map = new int[N+1][N+1];
        
        //사과 정보를 배열에 기록.
		st = new StringTokenizer(br.readLine());
		int K = Integer.parseInt(st.nextToken());
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			int row = Integer.parseInt(st.nextToken());
			int col = Integer.parseInt(st.nextToken());
            
			map[row][col] = 1;
		}
        
        //움직일 정보를 map에 넣음.
		Map<Integer, String> mapTime = new HashMap<Integer, String>();
		st = new StringTokenizer(br.readLine());
		int L = Integer.parseInt(st.nextToken());
		for (int i = 0; i < L; i++) {
			st = new StringTokenizer(br.readLine());
			int sec = Integer.parseInt(st.nextToken());
			String turnDir = st.nextToken();
            
			mapTime.put(sec, turnDir);
		}
		
        //앞으로의 경로와 이전의 경로들을 기록 -> 뱀을 arrayList로 만들어서 관리해도 됨.
		Queue<Dot> route = new LinkedList<Dot>();
		ArrayList<Dot> pastRoute = new ArrayList<Dot>();
		int lengthSnake = 1;
		int sec = 0;
        
		route.add(new Dot(1,1));
        pastRoute.add(new Dot(1,1));
		
		boolean isDone = false;
		
		while(!route.isEmpty() && !isDone) {
			
			Dot cur = route.poll();
			sec++;
			int nextRow = dir[curDir][0] + cur.row;
			int nextCol = dir[curDir][1] + cur.col;
			
			if(nextRow<= 0 || nextCol <= 0 || nextRow >N || nextCol >N)    break;
			
			//몸체랑 만나는지 검증
			for (int i = pastRoute.size()-1; i > pastRoute.size()-lengthSnake-1; i--) {
				Dot prevSnake = pastRoute.get(i);
				if(prevSnake.row == nextRow && prevSnake.col == nextCol) {
					isDone = true;
				}
			}
			
            //사과를 만났다면 사과를 먹으며 성장.
			if(map[nextRow][nextCol] == 1) {
				map[nextRow][nextCol] = 0;
				lengthSnake++;
			}
            
            //다음 경로로 머리 이동 및 이동 경로를 기록
			route.add(new Dot(nextRow, nextCol));
			pastRoute.add(new Dot(nextRow, nextCol));
			
            //다음 경로에서 방향이 바뀐다면 바뀌는 방향을 기록하여 리턴 -> 메서드로 분리해도 될듯.
			if(mapTime.containsKey(sec)) {
				String turnDir = mapTime.get(sec);
				if("D".equals(turnDir)) curDir = (curDir+1) %4;
				else if("L".equals(turnDir)) curDir = (curDir+3)%4;
			}
			
		}
		
		System.out.println(sec);
		
	}
}
class Dot{
	int row;
	int col;
	Dot(int row, int col) {
		this.row = row;
		this.col = col;
	}
}