백준[3190] 뱀

박지호·2022년 8월 9일
0

백준 3190 뱀

Language

Java 이용

Input

보드 크기 (N*N)
사과 개수
사과 위치
방향 전환 횟수
방향 전환 정보 (A B 형태로 입력 ; A: 게임 시작 A초 후에는 B로 방향을 바꿔준다.)

Output

게임 종료 시각(초)

Point

작동 방식은 문제에 자세히 나와있으니 참고하면 된다!

이 문제의 포인트는 뱀은 한 칸만 차지하지 않을 수도 있다는 것. 사과를 먹게 될 경우 뱀의 길이가 길어진다는 것이다. 즉, 뱀의 위치를 저장해주어야 한다.
또한 뱀의 머리가 있는 위치와 꼬리가 있는 위치를 구분할 수 있어야 한다.

따라서 deque를 사용해준다. deque는 앞과 뒤 양방향에서 삽입연산과 삭제 연산이 가능하다.

필자의 경우 꼬리의 좌표는 맨 앞에, 머리의 좌표는 맨 뒤에 위치하도록 하였다.

Code

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

class position{
	int x, y;
	public position(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

public class Main {
	public static Deque<position> snake; //뱀 몸의 위치 정보를 담는다.
	public static int result = 0; // 결과
	public static boolean finish; //게임이 끝났는지
	public static int N; //보드의 크기
	public static int[][] board; //보드의 상태 저장
	public static char d; // 현재 이동 방향
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine()); //보드의 크기
		int K = Integer.parseInt(br.readLine()); //사과의 개수
		
		board = new int[N+1][N+1]; // 보드 만들기
		
		//사과의 위치
		for(int i = 0; i<K;i++) {
			String[] sp = br.readLine().split(" ");
			
			int a = Integer.parseInt(sp[0]);
			int b = Integer.parseInt(sp[1]);
			
			board[a][b] = 1; //사과가 있는 위치에는 1을 넣어준다.
		}
		
		//뱀 초기 위치 (1,1)을 넣는다.	
		snake = new ArrayDeque<>();
		snake.add(new position(1,1));
		board[1][1] = -1;
		
		d = 'R'; // d : 오른쪽(R) 왼쪽(L) 위쪽 (U) 아래쪽 (D)
		int L = Integer.parseInt(br.readLine());

		finish = false; //게임이 끝났는지 체크
		int before = 0;		
		
		for(int i = 0; i<L;i++) {
			String[] sp = br.readLine().split(" ");
			int a = Integer.parseInt(sp[0]);
			char direc = sp[1].charAt(0);
			
			//현재 방향으로 a초만큼 이동해준다.
			for(int k = 0; k<a-before;k++) {
				moving();
				if(finish) break;
			}
			//이동이 끝난 후에는 이동 방향을 바꿔준다.
			d = (direc == 'L')?L_direc(d) : D_direc(d);
			
			before = a;
			//만약에 게임이 끝났다면 반복문 종료
			if(finish) break;
		}
		
		while(!finish) {
			moving();
		}
		
		
		bw.write(result+"\n");
		bw.flush();
	}
	
    //오른쪽으로 방향 전환 (90도)
	public static char D_direc(char now) {
		if(now == 'R') return 'D';
		else if(now == 'L') return 'U';
		else if(now == 'D') return 'L';
		else return 'R';
	}
	
    //왼쪽으로 방향 전환 (90도)
	public static char L_direc(char now) {
		if(now == 'R') return 'U';
		else if(now == 'L') return 'D';
		else if(now == 'D') return 'R';
		else return 'L';
	}
	
    //한 칸 이동
	public static void moving() {
		//아직 살아있다면 1초 ++
		result += 1;
		
		//맨 마지막에 있는 element가 뱀의 머리
		int temp_x = snake.peekLast().x;
		int temp_y = snake.peekLast().y;
		int nx = temp_x;  int ny = temp_y;
        
		//오른쪽으로 이동
		if(d == 'R') {
			ny += 1;
		}
		//왼쪽으로 이동
		else if(d == 'L') {
			ny -= 1;
		}
		//위로 이동
		else if(d == 'U') {
			nx -= 1;
		}
		//아래로 이동
		else {
			nx += 1;
		}
		
		//벽에 부딪힌다면 게임 종료
		if(nx <= 0 || ny<= 0 || nx > N || ny > N) {
			finish = true; return;
		}
		
		//자신과 부딪힌다면 게임 종료
		if(board[nx][ny] == -1) {
			finish = true; return;
		}
		//보드에 사과가 있다면
		if(board[nx][ny] == 1) {
			
			snake.addLast(new position(nx,ny)); //머리만 그 칸으로 옮겨준다.
			board[nx][ny] = -1; //해당 칸에 뱀의 몸이 위치함을 체크한다.
		}
		
		//사과가 없다면
		else {
			position tail = snake.removeFirst(); //꼬리가 위치한 칸을 비워주고
			board[tail.x][tail.y] = 0; //이제 해당 칸에는 뱀이 없으므로 0으로 바꿔준다.
			snake.addLast(new position(nx,ny)); //머리를 그 칸으로 이동시킨다.
			board[nx][ny] = -1;
		}
	}

}

check

  • deque를 사용해보자.
  • 시뮬레이션.

0개의 댓글