(JAVA) 백준 3190번 : 뱀

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

3190번: 뱀

 

 

시뮬레이션 문제이다.

 

고전 게임 중 이런 게임이 있지 않았나...?

 

 

 

아무튼

 

바로 설명 진행하겠다.

 

 

 

매커니즘

---

특이사항을 살펴보자.

 

 

 

1. 게임이 종료되는 조건 : 1) 벽에 닿거나 2) 자기 자신의 몸과 부딪혔을 때

2. 이동 방향을 변경할 수 있음 : "L" 은 왼쪽으로 90도, "D" 는 오른쪽으로 90도.

3. 사과가 존재 : 몸 길이가 늘어남. 사과를 먹은 위치에 몸통 생성되는 것과 같음

3-1. 사과가 존재하지 않음 : 꼬리가 사라짐. 몸 길이는 그대로.

 

- 출력 : 게임이 종료되었을 때 진행 시간

 

 

저 3가지를 각각 구현한 방법을 적자면

 

 

1번

1) x, y의 인덱스가 0 이하이거나 n 초과인 경우 종료 (인덱스 : 1 ~ N)

2) x, y 인덱스에 해당하는 위치에 내 몸이 있는지 없는지 판단하기 위해 map 원소 값을 보고 판별.

이후 설명할 거지만 간단히 말하면 

 

map에서

 

0 = 빈 공간 

1 = 사과 존재

2 = 몸통 존재

 

로 정한 후 해당 위치의 값이 2이면 종료하는 방식으로 진행했다.

 

2번

이동 방향을 나타내는 int 변수 생성. 

이동 방향에 따른 x, y 값 int 배열 생성. 시간 순서.

ex) moveX = { 0, 1, 0, -1 }; // 상, 우, 하, 좌

 

그래서

 

왼쪽으로 90도 이동해야 할 경우

(이동 방향 인덱스 - 1) % 4 인 값을 다음 인덱스로

** 만약 인덱스가 0이었으면 다시 4로 변경한 다음 수식을 진행해야 한다.

 

오른쪽으로 90도 이동해야 할 경우

(이동 방향 인덱스 + 1) % 4 인 값을 다음 인덱스로

 

변경한다.

 

또한, 시간과 이동 방향 문자 를 HashMap<Integer, String> 에 put해뒀었던 것을 

containsKey() 로 바꿔야하는 시간이 되었을 때 remove()로 꺼내서 

왼 또는 오 에 맞게 위 식으로 계산하면 된다.

 

 

 

 

3번

map[y][x] == 1 인 경우에 사과가 존재함.

 

사과 존재 -> 꼬리 제거 후 해당 위치에 몸통 생성

 

뱀 몸통의 x, y 좌표를 나타내는 클래스 객체를 만들어 별도의 Queue에 저장한 다음

 

꼬리 제거 시 가장 첫 번째 원소를 poll() 하면 끝!

 

반대로 몸통 생성 시 

add 함수를 통해 맨 끝에 원소를 추가한다.

 

 

 

 

감사합니다.

 

 

소스코드

---

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.HashMap;
	import java.util.LinkedList;
	import java.util.Queue;
	import java.util.StringTokenizer;
	// 뱀
	// 시뮬레이션
	public class p3190 {
	static int[][] map; // 0: 빈칸, 1: 사과 존재 2: 몸통 존재
	static int[] moveX = { 0, 1, 0, -1 }; //상우하좌
	static int[] moveY = { -1, 0, 1, 0 };
	static HashMap<Integer, String> move;
	static Queue<Snake> mySnake;
	static int nowDirection = 1; // 현재 뱀의 이동 방향
	public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	int n = Integer.valueOf(st.nextToken());
	map = new int[n + 1][n + 1]; // 인덱스 : 1 ~ N
	move = new HashMap<Integer, String>();
	mySnake = new LinkedList<Snake>();
	st = new StringTokenizer(br.readLine());
	int k = Integer.valueOf(st.nextToken()); // 사과의 개수
	// 맵에 사과 넣기
	while(k --> 0) {
	st = new StringTokenizer(br.readLine());
	int y = Integer.valueOf(st.nextToken());
	int x = Integer.valueOf(st.nextToken());
	map[y][x] = 1;
	}
	st = new StringTokenizer(br.readLine());
	int l = Integer.valueOf(st.nextToken()); // 뱀의 방향 변환 횟수
	// 이동 방향 바뀌는 시간과 이동 방향 담기
	while(l --> 0) {
	st = new StringTokenizer(br.readLine());
	int time = Integer.valueOf(st.nextToken());
	String c = st.nextToken();
	move.put(time, c);
	}
	// Arrays.sort(move.keySet().toArray()); // 시간 순 오름차순 정렬
	mySnake.add(new Snake(0, 0));
	int finishTime = start(2, 1, n);
	System.out.println(finishTime);
	}
	static int start(int x, int y, int n) {
	int nowTime = 1;
	while(true) {
	// System.out.println(x + " , " + y + " : " + nowTime);
	// 뱀이 벽에 부딪힌 경우
	if((x <= 0 || x > n) || (y <= 0 || y > n)) {
	return nowTime;
	}
	if(map[y][x] == 2) {
	return nowTime;
	}
	if(map[y][x] == 0) { // 꼬리 제거
	Snake tail = mySnake.poll();
	map[tail.y][tail.x] = 0;
	}
	mySnake.add(new Snake(x, y)); // 머리 추가
	map[y][x] = 2;
	if(move.containsKey(nowTime)) {
	String c = move.remove(nowTime);
	if(c.equals("L")) {
	nowDirection = nowDirection == 0 ? (moveX.length - 1) % 4 : (nowDirection - 1) % 4;
	}
	if(c.equals("D")) {
	nowDirection = (nowDirection + 1) % 4;
	}
	}
	// System.out.println(x + " , " + y + " : " + nowTime + ",, direction : " + nowDirection);
	x += moveX[nowDirection];
	y += moveY[nowDirection];
	nowTime++;
	}
	}
	}
	class Snake {
	int x;
	int y;
	Snake(int x, int y) {
	this.x = x;
	this.y = y;
	}
	}

view raw p3190.java hosted with ❤ by GitHub