[삼성 SW 역량 테스트 기출 문제집] 백준 3190 뱀

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

3190번: 뱀

백준 3190 뱀

 

시뮬레이션 문제로, 문제를 잘 파악하는 것이 중요하다.

 

먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
=> 여기서 큐를 쓰면 위의 규칙을 쉽게 구현할 수 있음. 먼저 다음칸에 위치할 때, 큐에 현재 위치를 넣고 

사과가 없을 경우에는 큐에서 poll로 빼준다..

 

나머지 부분은 주어진 조건대로 뱀의 방향을 하면서, 몸에 닿는 지 보드의 끝으로 가는 지 확인해주면 된다.

 

 

 

 

	public class BOJ_3190 {
	static int N;
	static ArrayList<Point> apple = new ArrayList<Point>();
	static Queue<Point> baem = new LinkedList<Point>();
	static int d [] = {1,2,3,4};
	static int direct [];
	static int timeX [];
	static int flag = 0;
	static int headx, heady;
	public static void main(String[] args) {
	// TODO Auto-generated method stub
	Scanner sc = new Scanner(System.in);
	N = sc.nextInt();
	int K = sc.nextInt();
	for(int i=0;i<K;i++){
	int x = sc.nextInt();
	int y = sc.nextInt();
	apple.add(new Point(x,y));
	}
	int L = sc.nextInt();
	direct = new int[L];
	timeX = new int [10001];
	for(int i=0;i<L;i++){
	int x = sc.nextInt();
	String input = sc.next();
	int c;
	if(input.equals("L")){
	c = 1;
	} else {
	c = 0;
	}
	direct[i] = c;
	timeX [i] = x;
	}
	baem.add(new Point(1,1,1));
	int time = 0;
	int idx = 0;
	int hd = 1;
	headx = 1;
	heady = 1;
	while(true){
	time++;
	if(idx < L && time==timeX[idx]+1){
	if(direct[idx]==1){
	if(hd==1){ // 오른쪽
	hd = 2;
	}
	else if(hd==2){ // 상
	hd = 4;
	} else if(hd==3){ // 하
	hd = 1;
	} else { // 좌
	hd = 3;
	}
	} else {
	if(hd==1){ // 오른쪽
	hd = 3;
	}
	else if(hd==2){ // 상
	hd = 1;
	} else if(hd==3){ // 하
	hd = 4;
	} else { // 좌
	hd = 2;
	}
	}
	idx++;
	}
	go(hd);
	if(flag==1){
	break;
	}
	}
	System.out.println(time);
	}
	public static void go(int direct){
	if(direct==1){
	heady++;
	} else if(direct==2){
	headx--;
	} else if(direct==3){
	headx++;
	} else {
	heady--;
	}
	if(headx == N+1 || heady == N+1 || headx==0 || heady==0) {
	flag = 1;
	return ;
	}
	for(Point i : baem){
	if(i.x==headx && i.y==heady){
	flag = 1;
	return ;
	}
	}
	baem.add(new Point(headx, heady, direct));
	int check = 0;
	for(Point i : apple){
	if(i.x==headx && i.y==heady){
	apple.remove(i);
	check = 1;
	break;
	}
	}
	if(check==0) {
	baem.poll();
	}
	}
	public static class Point {
	int x;
	int y;
	int direct;
	Point(int x,int y){
	this.x = x;
	this.y = y;
	}
	Point(int x, int y, int direct){
	this.x = x;
	this.y = y;
	this.direct = direct;
	}
	}
	}

view raw BOJ_3190.java hosted with ❤ by GitHub