[백준 3190]뱀/삼성 sw역량 테스트 기출(java)

문제 보러 가기

3190번: 뱀

이 문제는 익숙한 게임을 이용한 문제이다. 아래의 규칙을 통해 게임이 몇 초동안 지속될 수 있는지를 구하면 된다.

 

 

 

 

 

 

문제풀이

-map [][]에서 사과가 있는 인덱스는 1로 , 뱀이 위치하는 부분은 2로 기록한다. 

 

- Deque <int []> snake에 뱀의 위치를 기록한다.

-> 사과를 먹으면 사과를 먹은 머리 부분이 늘어남 => addFirst()

-> 사과가 없다면 꼬리 부분이 줄어듦 => pollLast()

 

-뱀이 사과를 먹으면 해당부분은 뱀이 위치하므로 -> map [x][y] = 2

-뱀의 꼬리가 줄어들는 부분은 사과도 없고 뱀도 없으므로 -> map [x][y] = 0

 

-방향은 큐에 담아 시간 == 방향 바꾸는 시간(peek().time) 이면 바꾼다. 

-> x초가 끝난 이후에 변화하는 것이므로 기존의 방향대로 time까지 오고 time+1을 새로운 방향으로 가게 된다.

 

-인덱스+1 => 오른쪽 90도, 인덱스-1 => 왼쪽 90도가 되게 dx [], dy []을 지정한다.

-> 여기서 왼쪽, 오른쪽 마지막 인덱스 부분을 잘 설정해줘야 한다.

if(direction.dir.equals("L"))
	dir = dir == 0 ? 3 : (dir-1)%4; //왼쪽 3->2->1->0->3-> ..
else
	dir = (dir+1)%4; //오른쪽 0->1->2->3->0->...

 

 

-뱀의 머리가 뱀의 몸에 닿거나 map [x][y] == 2 , 벽일 경우 => 인덱스를 벗어나는 경우 종료.

 

 

 

 

 

 

 

 

 

public class Ex_3190 {
	
	static int[][] map;
	static int n,time;
	static Queue<Direction> dirQ = new LinkedList<>();
	static Deque<int[]> snake = new ArrayDeque<>(); 
	static int[] dx = {0,1,0,-1};
	static int[] dy = {1,0,-1,0};
	public static void main(String args[]) throws Exception{
		//삼성 sw 역량테스트 뱀
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		n = Integer.parseInt(br.readLine());
		map = new int[n+1][n+1];
		
		int k = Integer.parseInt(br.readLine());
		while(k-- > 0) {
			st = new StringTokenizer(br.readLine());
			int row = Integer.parseInt(st.nextToken());
			int col = Integer.parseInt(st.nextToken());
			map[row][col] = 1; //사과 체크
		}
		
		int l = Integer.parseInt(br.readLine());
		while(l-- > 0 ) {
			st = new StringTokenizer(br.readLine());
			int time = Integer.parseInt(st.nextToken());
			String dir = st.nextToken();
			dirQ.add(new Direction(time,dir)); //방향 바꾸는 시간, 방향 L || D
		}
		snake.add(new int[] {1,1}); //뱀의 첫시작 위치
		map[1][1]=2;// 뱀위치는 2로 기록
		time=1;
		int dir = 0;
		while(true) {
			dir = go(dir); //해당 방향으로 이동
			if(dir == -1 ) //종료조건일 경우
				break;
			time++;
		}
		System.out.println(time);
	}
    //이동 후 다음 가야될 방향을 return
    //-1일 경우 종료
	static int go(int dir) {
		int[] head = snake.peekFirst();		
		int x = head[0]+dx[dir];
		int y = head[1]+dy[dir];
		
		if(x <= 0 || y <= 0 || x > n || y > n ) 
			return -1;
		//뱀의 머리가 몸에 닿을 경우
		if(map[x][y]==2)
			return -1;
		//비어 있는칸일 경우 꼬리를 줄임
		if(map[x][y]==0) {
			int[] tail = snake.pollLast();
			map[tail[0]][tail[1]]=0;
		}
        //머리를 추가, 뱀 위치를 map에 기록
		snake.addFirst(new int[] {x,y});
		map[x][y]=2;
		
		
		//방향 - time초가 끝난 후에 방향바꾸기
		if(!dirQ.isEmpty() && dirQ.peek().time == time) {
			Direction direction = dirQ.poll();
			if(direction.dir.equals("L"))
				dir = dir == 0 ? 3 : (dir-1)%4;
			else
				dir = (dir+1)%4;
		}
		return dir;
		
	}
	static class Direction{
		int time;
		String dir;
		
		Direction(int time, String dir){
			this.time = time;
			this.dir = dir;
		}
	}
}