(알고리즘) boj - 뱀 (3190)

www.acmicpc.net/problem/3190

3190번: 뱀

---

풀이 과정

문제 설명 

• 벽을 만나거나 뱀 자신에게 닿으면 종료
• 다음칸에 사과가 있다면 뱀의 길이를 늘린다.
  • 뱀의 머리를 사과 있는 칸으로 머리를 이동
• 다음칸에 사과가 없다면 뱀의 길이를 늘리지 않는다.
  • 뱀의 꼬리를 자르고 사과 있는 칸으로 머리를 이동
• 특정 시간에 VALUE가 D이면 머리를 우측으로 L이면 좌측으로 이동 
  • 머리 회전은 이동 후에 진행된다.

 

필자는 벽과 뱀이 지나간 자리를 모두 2로 설정하였고 다음칸이 2면 종료하도록 설정하였다.

또한 뱀의 꼬리와 머리를 각각의 상황별로 add 시키기 위해서 Deque를 사용하였다.

 

private static int[][] direction = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

처음 머리 진행방향은 1, 0 이므로 (1번째 인덱스) 

D 이면 현재 진행 방향에서 + 1을 해서 4로 나는 나머지로 방향을 구했다.

L 이면 현재 진행 방향에서  + 3을 해서 4로 나눈 나머지로 방향을 구했다.

 

한 번씩 그려보면 이해가 빠를 것이다.

 

또한 다음 진행 방향을 map [nextX][nextY]로 한 것이 아닌 map [nextY][nextX]로 지정한 것이 특징이다.

사실 이 부분이 가장 이해가 안 되었다. 이유는 이동 방향을 좌표상으로 생각하였기 때문이다. 좌표가 아닌 행렬에서 이동하는 것인데 말이다.

---

소스 코드

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Snake {
	private static int size;
	private static int[][] map; 
	private static Map<Integer, String> rotation;
	private static int[][] direction = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		size = scanner.nextInt();
		map = new int[size+2][size+2];
		
		// 벽은 2로 지정
		for (int i = 0; i < size + 2; i++) {
			map[0][i] = 2;
			map[i][0] = 2;
			map[i][size+1] = 2;
			map[size+1][i] = 2;
		}
		
		// 사과 위치는 1로 지정
		int appleSize = scanner.nextInt();
		for (int i = 0; i < appleSize; i++) {
			int appleX = scanner.nextInt();
			int appleY = scanner.nextInt();
			map[appleX][appleY] = 1;
		}
		
		
		// 회전 정보 지정
		int whereSize = scanner.nextInt();
		scanner.nextLine();
		rotation = new HashMap<Integer, String>();
		for (int i = 0; i < whereSize; i++) {
			String[] str = scanner.nextLine().split(" ");
			rotation.put(Integer.parseInt(str[0]), str[1]);
		}
		
		Deque<Point> snake = new ArrayDeque<>();
		snake.addFirst(new Point(1, 1));
		int where = 1;
		int time = 1;
		
		while(true) {
			Point point = snake.peekLast();
			
			int startX = point.getX();
			int startY = point.getY();
			
			
			int nextX = startX + direction[where][0];
			int nextY = startY + direction[where][1];
			
			// 벽에 부딪히거나 자신에게 닿으면 2
			if (map[nextY][nextX] == 2) {
				break;
			}
						
			//사과가 없는경우
			if (map[nextY][nextX] != 1) {
				Point tail = snake.pollFirst();
				int tailX = tail.getX();
				int tailY = tail.getY();
				
				map[tailY][tailX] = 0;
			}
			
			map[nextY][nextX] = 2;
			snake.addLast(new Point(nextY, nextX));
			
			if(rotation.containsKey(time)) {
				String direct = rotation.get(time);
				
				where = direct.equals("D") ? (where + 1) % 4 : (where + 3) % 4;
			}
			
			time += 1;
			
		}
		System.out.println(time);
	}

}
class Point {
	private final int x;
	private final int y;
	
	public Point(int y, int x) {
		super();
		this.x = x;
		this.y = y;
	}

	public int getX() {
		return x;
	}

	public int getY() {
		return y;
	}
	
}