[백준][JAVA] 3190 - 뱀

정말 오랜만에 올리는 포스팅입니다.
백준 알고리즘 문제를 하나 풀어보도록 하겠습니다.

---

 

3190번: 뱀

 

 

 

개요

골드 4 난이도 시뮬레이션 문제입니다.

골드 난이도라지만 복잡한 알고리즘 지식이 필요한 문제는 아닙니다.
이차원 배열과 큐 Queue 정도의 자료구조를 문제풀이에 응용할 줄 알고,

문제의 요구사항을 꼼꼼히 구현하는 능력이 있다면 풀 수 있는 문제였습니다.

 

 

코드

[제출 결과]

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_3190_뱀 {

	static int[] dR = { 0, 1, 0, -1 };
	static int[] dC = { 1, 0, -1, 0 };

	static int[][] board;
	static int N;
	static boolean over;

	static int dir;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		int K = Integer.parseInt(br.readLine());

		board = new int[N + 1][N + 1];

		StringTokenizer st;
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			board[r][c] = 1;

		}

		int L = Integer.parseInt(br.readLine());

		
		int r = 1, c = 1;
		int[] tail;

		dir = 0;
		over = false;
		int elapsed = 0;

		Queue<int[]> snake = new ArrayDeque<>();
		snake.offer(new int[] { r, c });
		board[r][c] = -1;

		

		st = new StringTokenizer(br.readLine());
		int X = Integer.parseInt(st.nextToken());
		char cmd = st.nextToken().charAt(0);

		while (!over) {
			
			r += dR[dir];
			c += dC[dir];

			++elapsed;
			if (over = isOuttaBound(r, c))
				break;

			if (board[r][c] == 1) {
				snake.offer(new int[] { r, c });
				board[r][c] = -1;
			} else if (board[r][c] == 0) {
				snake.offer(new int[] { r, c });
				board[r][c] = -1;

				tail = snake.poll();
				board[tail[0]][tail[1]] = 0;

			} else if (board[r][c] == -1) {
				over = true;
				break;
			}
			
			if (elapsed == X) {
				redirect(cmd);

				if(--L > 0) {
					st = new StringTokenizer(br.readLine());
					X = Integer.parseInt(st.nextToken());
					cmd = st.nextToken().charAt(0);
				}else X = -1;	
			}
		}

		System.out.println(elapsed);

	}

	static boolean isOuttaBound(int r, int c) {
		if (r < 1 || c < 1 || r > N || c > N)
			return true;
		return false;
	}

	static void redirect(char cmd) {
		switch (cmd) {
		case 'L':
			dir = (dir + 3) % 4;
			break;

		case 'D':
			dir = (dir + 1) % 4;
			break;
		}
	}

}

 

상세

[Queue 활용]

뱀의 움직임은 Queue를 이용해 표현할 수 있습니다. Queue 내부에는 행/열을 나타내기 위해 2칸짜리 정수 배열을 저장했습니다.

뱀의 기본 동작은 선입선출 FIFO 구조의 큐로 표현할 수 있습니다.

‘새롭게 한 칸이 추가되면, 가장 오래된 한 칸이 빠져나가는’ 패턴을 갖기 때문입니다.
뱀이 현재 이차원 배열 위에서 차지하고 있는 위치 정보가 필요하기 때문에,

큐에는 행 값과 열  값이 들어갈 수 있는 정수 배열을 저장하겠습니다.

 

 

 

 

이차원 배열 board 위에서 뱀의 현재 위치는 -1, 사과는 1로 표현됩니다.

[게임판 구성]

이차원 int 배열로 표현합니다. 뱀의 인덱스가 1로 주어지기 때문에 크기는 N+1로 설정합니다.

• 0 : 아무것도 없는 빈 칸입니다. 배열을 생성할 때 자동으로 할당되는 값인 0으로 표현합니다.
• 1 : 사과의 위치를 입력받아 게임판에 1로 표현하겠습니다.
• -1 : 현재 뱀의 위치를 나타냅니다. 뱀의 다음 위치가 이곳이라면 게임이 종료됩니다.

 

 

[뱀의 동작 구현]

델타 탐색을 이용하여 현재 위치에서 지정된 방향으로 r값 또는 c값을 한 칸 전진시킵니다.

• 0을 만난 경우 :
  • [크기 1 늘리기] 새로운 위치 좌표를 큐에 넣고, 게임판에서 해당 위치를 -1로 표시합니다.
  • [크기 1 줄이기] 큐에서 가장 오래된 위치 좌표를 제거하고, 게임판에서 해당 위치를 0으로 되돌립니다.
• 1을 만난 경우 :
  • [크기 1 늘리기] 새로운 위치 좌표를 큐에 넣고, 게임판에 해당 위치를 -1로 표시합니다.
  • [크기 1 줄이기] 사과를 먹어서 전체 크기가 1 증가하므로, 크기를 줄이는 동작을 실행하지 않습니다.
• -1을 만난 경우 / 맵 밖으로 벗어난 경우
  • 게임 종료 조건입니다. 반복문을 종료하고 경과한 시간을 출력합니다.

 

일정 시간이 될 때마다 델타 탐색 배열의 인덱스를 바꿔 이동 방향을 전환합니다.

 

주의할 점

입력값으로 들어오는 행, 열 위치는 0이 아니라 1부터 시작하는 인덱스로 제시됩니다.
배열 크기 설정과 종료조건 설정에 유의하도록 합니다.

 

 

---

 

코드와 관련된 피드백이나 질문이 있으시면 댓글 부탁드립니다.