뱀

🔗문제 링크

구현 코드

import java.util.*;

public class Solution {
	static int n;
	static int[][] board;
	// 상하좌우 1 2 3 4
	static int snake_dir = 4; // 기본 방향 오른쪽
	static int[][] check; // 뱀이 있는 위치 체크
	static Deque<Point> moveQueue = new LinkedList<>();

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.nextInt(); // 보드 크기
		board = new int[n][n];
		int k = in.nextInt(); // 사과 개수
		for (int i = 0; i < k; i++) {
			int row = in.nextInt()-1;
			int col = in.nextInt()-1;
			board[row][col] = -1; // 사과 표시
		}

		int l = in.nextInt(); // 뱀의 방향정보 개수
		Queue<Move> q = new LinkedList<>();
		for (int i = 0; i < l; i++) {
			int t = in.nextInt();
			char dir = in.next().charAt(0);
			q.add(new Move(t, dir));
		}

		// 시뮬레이션 시작
		check = new int[n][n];
		check[0][0] = 1;
		moveQueue.add(new Point(0, 0));
		long answer = 0; // 게임 시간

		//문제1:q가 비지 않을때까지로 조건 걸어놔서 문제였음
		while (true) {
			// 방향으로 한칸 이동
			answer++;
			boolean result = move();
			if (!result) 
				break;
			
			if (!q.isEmpty()) {
				if (answer == q.peek().t) {
					// 방향변경
					changeDirection(q.poll().dir);
				}
			}
		}

		System.out.println(answer);
	}

	static boolean move() { // 한칸 이동
		Point head = moveQueue.peekFirst();
		Point tail = moveQueue.peekLast();

		if (snake_dir == 1) {
			// 상
			if (head.row - 1 >= 0 && head.row - 1 < n && head.col >= 0 && head.col < n
					&& check[head.row - 1][head.col] != 1) {
				check[head.row - 1][head.col] = 1;
				moveQueue.addFirst(new Point(head.row - 1, head.col));
				if (board[head.row - 1][head.col] == -1) {
					// 사과
					board[head.row - 1][head.col] = 0;
				} else {
					// 사과 x
					moveQueue.pollLast();
					check[tail.row][tail.col] = 0;
				}


			} else
				return false;

		} else if (snake_dir == 2) {
			// 하
			if (head.row + 1 >= 0 && head.row + 1 < n && head.col >= 0 && head.col < n
					&& check[head.row + 1][head.col] != 1) {
				check[head.row + 1][head.col] = 1;
				moveQueue.addFirst(new Point(head.row + 1, head.col));
				if (board[head.row + 1][head.col] == -1) {
					// 사과
					board[head.row + 1][head.col] = 0;
				} else {
					// 사과 x
					moveQueue.pollLast();
					check[tail.row][tail.col] = 0;
				}

			} else
				return false;
		} else if (snake_dir == 3) {
			// 좌
			if (head.row >= 0 && head.row < n && head.col - 1 >= 0 && head.col - 1 < n
					&& check[head.row][head.col - 1] != 1) {
				check[head.row][head.col - 1] = 1;
				moveQueue.addFirst(new Point(head.row, head.col - 1));
				if (board[head.row][head.col - 1] == -1) {
					// 사과
					board[head.row][head.col - 1] = 0;
				} else {
					// 사과 x
					moveQueue.pollLast();
					check[tail.row][tail.col] = 0;
				}

			} else
				return false;
		} else {
			// 우
			if (head.row >= 0 && head.row < n && head.col + 1 >= 0 && head.col + 1 < n
					&& check[head.row][head.col + 1] != 1) {
				check[head.row][head.col + 1] = 1;
				moveQueue.addFirst(new Point(head.row, head.col + 1));
				if (board[head.row][head.col + 1] == -1) {
					// 사과
					board[head.row][head.col + 1] = 0;
				} else {
					// 사과 x
					moveQueue.pollLast();
					check[tail.row][tail.col] = 0;
				}

			} else
				return false;
		}
		return true;
	}

	static void changeDirection(char dir) { // 방향 변경
		if (dir == 'L') {
			if (snake_dir == 1) {
				snake_dir = 3;
			} else if (snake_dir == 2) {
				snake_dir = 4;// 4
			} else if (snake_dir == 3) {
				snake_dir = 2;
			} else {
				snake_dir = 1;
			}
		} else {
			if (snake_dir == 1) {
				snake_dir = 4;
			} else if (snake_dir == 2) {
				snake_dir = 3;
			} else if (snake_dir == 3) {
				snake_dir = 1;
			} else {
				snake_dir = 2;
			}
		}
	}

	static class Point {
		int row;
		int col;

		public Point(int row, int col) {
			this.row = row;
			this.col = col;
		}
	}

	static class Move {
		int t;
		char dir;

		public Move(int t, char dir) {
			this.t = t;
			this.dir = dir;
		}
	}
}

• 알고리즘

  board: 사과 위치가 표시된 원래 배열
  check: 뱀의 이동위치를 표시할 배열
  moveQueue: 뱀의 몸 위치 정보들을 담고 있는(머리,몸,꼬리) 덱

while (true) {
			answer++;
			boolean result = move();
			if (!result) 
				break;
			
			if (!q.isEmpty()) {
				if (answer == q.peek().t) {
					// 방향변경
					changeDirection(q.poll().dir);
				}
			}
		}

이부분이 핵심 알고리즘이라고 할 수 있음. 한번 이동시 시간 증가시키고 만약 방향을 변경해야할 시간이 왔을때 방향을 변경해주면 됨. 또한 이동시 조건에 걸리는 경우(벽에 부딪히거나 자기 자신과 충돌) 멈추면 됨.

나는 각 방향에 대해서 회전하는 경우 방향처리를 따로 함수해서 if문으로 해줬는데 다른 블로그를 보니까 좀 더 효율적인 방법이 있었음. 나중에 그부분에 대해서 다시 생각해보고 다시 풀어봐야겠음.

문제 자체는 어렵지 않게 풀었음..하지만 나의 안일한 실수로 테스트 출력문을 안빼서 두시간동안 뻘짓했음.. ㅠ 모든 반례를 해도 다 맞는데 어쩐지 7%에서 자꾸 걸리는...하아 ㅠㅠㅠㅠ
다신 이런 실수 하지말자