백준 3190: 뱀[Gold 4] / Java

백준 3190: 뱀

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

 

문제 설명

'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

---

내 정답 코드

내 코드의 로직은 이렇다.

 

우선 뱀을 ArrayList<int[]> 형태로 선언하고, 뱀의 머리 좌표가 리스트의 가장 끝 인덱스에 위치시킨다.

매초마다 time으로 관리하며 게임 종료시까지 동작을 반복한다.

1. 이동 후의 뱀 머리 좌표 생성 (nr, nc)

2. 벽이나 몸통에 충돌하는지 체크

3. 이동한 칸에 사과가 있는지 체크

4. 사과 여부에 따라 꼬리 제거 or 유지

5. 회전 여부 체크

6. 시간 경과 (time+=1)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static int N, K, L;
	static int[][] apples;
	static String[][] turns;
	static ArrayList<int[]> snake;
	static int[] dr = { -1, 0, 1, 0 };
	static int[] dc = { 0, 1, 0, -1 };

	public static void main(String[] args) throws IOException {
		init();

		int tIdx = 0; // 방향전환 배열 추적 인덱스
		int time = 1; // 시간 흐름
		int dir = 1; // 시작은 오른쪽 방향
		out: while (true) {

			int nr = snake.get(snake.size() - 1)[0] + dr[dir];
			int nc = snake.get(snake.size() - 1)[1] + dc[dir];

			// 벽 체크
			if (nr < 1 || nr > N || nc < 1 || nc > N)
				break out;
			// 몸통 충돌 체크
			for (int[] pos : snake) {
				if (pos[0] == nr && pos[1] == nc)
					break out;
			}

			// 사과 있는지 체크
			boolean hadApple = false;
			for (int[] apple : apples) {
				if (apple[2] == 1 && apple[0] == nr && apple[1] == nc) {
					apple[2] = 0;
					hadApple = true;
					break;
				}
			}

			// 사과 안먹었으면 꼬리 제거
			if (!hadApple)
				snake.remove(0);


			// 이동
			snake.add(new int[] { nr, nc });

			// 방향전환 타이밍인지 체크
			if (tIdx < turns.length && time == Integer.parseInt(turns[tIdx][0])) {
				if (turns[tIdx][1].equals("L")) {
					dir = (dir + 3) % 4;
				} else {
					dir = (dir + 1) % 4;
				}
				tIdx += 1;
			}
			
			// 시간 경과
			time += 1;
		}

		System.out.println(time);
	}

	private static void init() throws IOException {
		N = Integer.parseInt(br.readLine());
		// 맨 마지막 인덱스가 뱀의 머리
		snake = new ArrayList<>(Arrays.asList(new int[] { 1, 1 }));

		K = Integer.parseInt(br.readLine());
		apples = new int[K][3];
		for (int i = 0; i < K; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			apples[i][0] = Integer.parseInt(st.nextToken());
			apples[i][1] = Integer.parseInt(st.nextToken());
			apples[i][2] = 1; // 사과 존재 여부 체크
		}

		L = Integer.parseInt(br.readLine());
		turns = new String[L][2];
		for (int i = 0; i < L; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			turns[i][0] = st.nextToken();
			turns[i][1] = st.nextToken();
		}
	}
}

---

개선 사항

다른 사람들의 코드를 보다 보니, 내 코드에서 실행속도를 개선시킬 수 있는 방법을 생각해냈다.

몸통 충돌 체크 & 사과 체크

board배열을 사용해 뱀 길이 전체를 순회하는 방식에서 바로 뱀 머리 좌표만 체크하는 방식으로 개선 가능하다.

또한 사과 체크 또한 뱀 머리좌표로 한번에 조회 가능.

O(len) > O(1) 로 개선!!

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static int N, K, L;
	static int[][] board;
	static String[][] turns;
	static ArrayList<int[]> snake;
	static int[] dr = { -1, 0, 1, 0 };
	static int[] dc = { 0, 1, 0, -1 };

	public static void main(String[] args) throws IOException {
		init();

		int tIdx = 0; // 방향전환 배열 추적 인덱스
		int time = 1; // 시간 흐름
		int dir = 1; // 시작은 오른쪽 방향
		while (true) {
			int r = snake.get(snake.size() - 1)[0];
			int c = snake.get(snake.size() - 1)[1];
			int nr = r + dr[dir];
			int nc = c + dc[dir];

			// 벽 체크
			if (nr < 1 || nr > N || nc < 1 || nc > N)
				break ;
			// 몸통 충돌 체크
			if (board[nr][nc] == 1) break;

			// 사과 있는지 체크
			boolean hadApple = false;
			if (board[nr][nc] == 2) {
				hadApple = true;
				board[nr][nc] = 0;
			}

			// 사과 안먹었으면 꼬리 제거
			if (!hadApple) {
				board[snake.get(0)[0]][snake.get(0)[1]] = 0;
				snake.remove(0);
			}

			// 이동
			snake.add(new int[] { nr, nc });
			board[nr][nc] = 1;
			

			// 방향전환 타이밍인지 체크
			if (tIdx < turns.length && time == Integer.parseInt(turns[tIdx][0])) {
				if (turns[tIdx][1].equals("L")) {
					dir = (dir + 3) % 4;
				} else {
					dir = (dir + 1) % 4;
				}
				tIdx += 1;
			}
			
			// 시간 경과
			time += 1;
		}

		System.out.println(time);
	}

	private static void init() throws IOException {
		N = Integer.parseInt(br.readLine());
		board = new int[N+1][N+1];
		board[1][1] = 1;
		// 맨 마지막 인덱스가 뱀의 머리
		snake = new ArrayList<>(Arrays.asList(new int[] { 1, 1 }));

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

		L = Integer.parseInt(br.readLine());
		turns = new String[L][2];
		for (int i = 0; i < L; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			turns[i][0] = st.nextToken();
			turns[i][1] = st.nextToken();
		}
	}
}

---

배운점

메모리를 아끼려고 board 배열을 생성하지 않았었는데,

오히려 하나의 배열로 상태 관리를 하는 것이 실행속도도 향상시켰다.

 

 

• board 하나로 사과·몸통 상태를 통합하니 판정이 O(1)로 단순해지고 코드도 깔끔해졌다.
• ArrayList 대신 Deque를 쓰면 양방향 삽입삭제가 필요할 때 더 효율적이다.