뱀

문제

언어

  • JavaScript

순서도

  1. 1 초 증가시키고, 뱀의 몸 길이를 1 증가시키고, 뱀의 머리를 다음 칸에 위치시킵니다.
  2. 이 때, 뱀의 머리가 위치한 칸에 사과가 있다면, 추가적으로 처리할 것은 없습니다.
  3. 이 때, 뱀의 머리가 위치한 칸에 사과가 없다면, 뱀의 몸의 길이를 1 감소시키고, 뱀의 꼬리를 한 칸 줄여줍니다.
  4. 현재의 초 (seconds) 에 방향 변환 정보가 있다면, 방향을 변환합니다.
  5. 1 ~ 4 번 과정을 수행하다가, 뱀의 머리가 벽 또는 자기자신의 몸에 부딪히면 종료하고, 그 때의 초 (seconds) 를 출력합니다.

문제 풀이 step 1

  • 큐를 이용해서 뱀의 몸통 정보를 기록하고, 문제에서 주어진 입력에 따라서 뱀의 이동을 시뮬레이션 하는 문제입니다.
  • 뱀은 매 초마다 다음과 같은 규칙을 따른다고 합니다.
    • 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
    • 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
    • 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
  • 위 규칙에 따라서 시뮬레이션 해주면 됩니다.

문제 풀이 step 2

  • 문제 해결 과정 속에서 3 가지 정보가 필요합니다.
    1. 뱀의 몸통 정보
      • 여기서 Queue 를 이용합니다.
      • 이동할 때, 뱀은 몸길이를 늘립니다. 따라서 Queue 에 뱀의 머리가 위치한 칸의 좌표를 넣어줍니다.
      • 만약 이동한 칸에 사과가 있다면, 뱀의 몸길이가 1 늘어나고, 꼬리는 움직이지 않으니, 추가적으로 처리할 것은 없습니다.
      • 만약 이동한 칸에 사과가 없다면, 뱀의 몸길이를 1 줄이고, 꼬리가 위치한 칸을 비워줘야 해서, Queue 에서 뱀의 꼬리 좌표를 빼줍니다.
      • 이 과정 속에서, 뱀의 머리는 Queue 의 rear 에 위치하고, 뱀의 꼬리는 Queue 의 front 에 위치합니다.
    2. 뱀의 이동 정보
      • 여기서는 주어진 정사각 보드를 이용합니다. 보드 위에서 뱀이 위치한 부분을 2 로 설정합니다.
      • 보드에서 0 은 빈공간을, 1 은 사과를, 2 는 뱀의 위치를 나타내도록 설정합니다.
    3. 뱀의 방향 정보
      • 총 4 가지 방향 (상, 우, 하, 좌) 를 설정합니다.
      • 뱀의 시작 방향은 우 입니다.
        • 뱀의 방향 변환 정보가 ‘L’ 이면 반시계 방향으로 90 도 회전합니다. (우는 상으로)
        • 뱀의 방향 변환 정보가 ‘D’ 이면 시계 방향으로 90 도 회전합니다. (우는 하로)
  • 이 정보들을 이용해서 시뮬레이션 하다가, 뱀이 벽 또는 자기자신의 몸과 부딪히면 그 때의 초 (seconds) 를 출력해주면 됩니다.
  • 추가 설명은 주석에 작성하겠습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

// 간단한 Queue 구현
class Queue {
	constructor() {
		this.bucket = [];
		this.front = -1;
		this.rear = -1;
	}

	isEmpty() {
		return this.front === this.rear;
	}

	enqueue(data) {
		this.bucket[++this.rear] = data;
	}

	dequeue() {
		if (!this.isEmpty()) return this.bucket[++this.front];
	}
}

// 벽에 부딪히는지 검사하는 함수
const isPossibleRoute = (n, x, y) => 0 <= x && x < n && 0 <= y && y < n;

const solution = (input) => {
	const n = Number(input[0]);
	const board = Array.from({length: n}, () => Array(n).fill(0));
	const k = Number(input[1]);

	// 보드에 사과 위치 기록
	// board -> (0 : 빈 공간, 1 : 사과 위치, 2 : 뱀의 위치)
	for (let i = 2; i < 2 + k; i++) {
		const [x, y] = input[i].split(" ").map(Number);
		board[x - 1][y - 1] = 1;
	}

	const l = Number(input[2 + k]);
	// 뱀의 방향 변환 정보 기록
	const commands = input.slice(3 + k).map((v) => v.split(" "));

	// 뱀의 몸통을 기록하기 위한 queue
	const queue = new Queue();

	// 방향 정보 (상, 좌, 하, 우)
	const cx = [-1, 0, 1, 0];
	const cy = [0, 1, 0, -1];

	// 시작 방향
	let [sx, sy] = [0, 0];
	let pos = 1;
	queue.enqueue([sx, sy]);

	// 1 초씩 늘리면서 뱀 이동 시뮬레이션
	// board -> (0 : 빈 공간, 1 : 사과 위치, 2 : 뱀의 위치)
	let seconds = 0;
	let index = 0;
	while (true) {
		// 다음 위치
		[sx, sy] = [sx + cx[pos], sy + cy[pos]];
		seconds += 1;

		// 벽이거나 뱀의 몸통인 경우 게임 끝
		if (!isPossibleRoute(n, sx, sy) || board[sx][sy] === 2) break;

		// 사과가 아닌 경우 뱀의 꼬리가 위치한 칸을 비워줌
		if (board[sx][sy] !== 1) {
			const [dx, dy] = queue.dequeue();
			board[dx][dy] = 0;
		}

		// 뱀이 몸길이를 늘려 머리를 다음 칸에 위치
		queue.enqueue([sx, sy]);
		board[sx][sy] = 2;

		if (index >= commands.length) continue;

		let [targetSeconds, direction] = commands[index];
		if (seconds === Number(targetSeconds)) {
			// 방향 변환 정보에 따라서 방향 전환
			if (direction === "L") pos = (pos + 3) % 4;
			else pos = (pos + 1) % 4;
			index += 1;
		}
	}

	// 게임이 끝난 시점의 초 (seconds) 를 출력
	return seconds;
};

console.log(solution(input));