[BOJ/Java] 3190 : 뱀

문제

 

www.acmicpc.net/problem/3190

3190번: 뱀

 

 

풀이

 

뱀이 사과를 먹으면 길이가 늘어나고, 주어진 시간과 방향대로 방향을 전환해야 하는 문제 / 종료 조건은 뱀이 범위를 벗어날 때와 자기 자신의 몸과 부딪힐 때

 

길이가 1인 사람? 동물? 이 움직이는 시뮬레이션만 하다가 뱀처럼 길이가 긴 친구를 움직이려니 감이 잘 안 잡혔다.. 처음에는 풀지 못했고, 친구와 스터디를 진행한 후에 뱀이 지나가고 있는 위치를 큐에 넣어두는 방법을 알게 됐다.

 

뱀이 이동하는 방식은 이동할 위치에 사과가 있는 경우와 없는 경우로 나뉘게 된다.

1. 사과가 있는 경우

- 이동할 위치의 좌표 노드를 큐에 넣어주고, 뱀의 길이가 늘어났기 때문에 꼬리 좌표를 빼내지 않는다

2. 사과가 없는 경우

- 이동할 위치의 좌표 노드를 큐에 넣어주고, 뱀의 길이는 그대로고 위치만 변한 것이기 때문에 꼬리 좌표를 빼낸다

- 이동할 위치가 이미 뱀이 있는 경우(자기 자신과 부딪힐 경우) 종료된다

 

이외에 뱀이 범위를 벗어나는 조건이나 정해진 시간에 도달하면 방향을 전환해주는 조건들을 잘 고려해 구현한다면 크게 어렵지는 않은 문제였다.

 

 

 

코드

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

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int[][] dir = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; // 북동남서
	static int N;
	static char[][] map;
	static Queue<dirChange> queue = new LinkedList<>();
	static Queue<Node> snake = new LinkedList<>();
	static int s_x, s_y; // 뱀 머리의 좌표
	static int direction = 1; // 뱀이 향하는 방향
	static int cnt;

	public static void main(String[] args) throws Exception {

		N = Integer.parseInt(in.readLine());
		map = new char[N + 1][N + 1];
		int appleCnt = Integer.parseInt(in.readLine());
		for (int i = 0; i < appleCnt; i++) {
			st = new StringTokenizer(in.readLine());
			map[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = 'A';
		}
		int turnCnt = Integer.parseInt(in.readLine());
		for (int i = 0; i < turnCnt; i++) {
			st = new StringTokenizer(in.readLine());
			queue.offer(new dirChange(Integer.parseInt(st.nextToken()), st.nextToken().charAt(0)));
		}
		s_x = 1;
		s_y = 1; // 초기 위치
		map[s_x][s_y] = 'X';
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (map[i][j] == '\u0000')
					map[i][j] = '.';
			}
		}

		snake.offer(new Node(s_x, s_y));
		cnt = 1;
		while (true) {

			s_x = s_x + dir[direction][0];
			s_y = s_y + dir[direction][1];
			if (isOutOfMap(s_x, s_y))
				break;
			if (map[s_x][s_y] == 'A') {
				map[s_x][s_y] = 'X';
				snake.offer(new Node(s_x, s_y));
			} else {
				if (map[s_x][s_y] == 'X')
					break; // 자기자신의 몸과 부딪히면
				map[s_x][s_y] = 'X';
				snake.offer(new Node(s_x, s_y));
				Node temp = snake.poll();
				map[temp.x][temp.y] = '.';

			}
			if (!queue.isEmpty()) {
				if (queue.peek().time == cnt) {
					if (queue.poll().dir == 'L') {// 왼쪽으로 방향 바꾸기
						direction = left(direction);
					} else {// 오른쪽으로 방향 바꾸기
						direction = right(direction);
					}
				}
			}
			// 디버깅
			// show();

			cnt++;
		}
		System.out.println(cnt);
	}

	static class Node {
		int x, y;

		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	static boolean isOutOfMap(int x, int y) {
		if (x < 1 || y < 1 || x > N || y > N)
			return true;
		return false;
	}

	static int left(int x) {
		if (x == 0)
			return 3;
		else if (x == 1)
			return 0;
		else if (x == 2)
			return 1;
		else
			return 2;
	}

	static int right(int x) {
		if (x == 0)
			return 1;
		else if (x == 1)
			return 2;
		else if (x == 2)
			return 3;
		else
			return 0;
	}

	public static void show() {
		System.out.println(cnt);
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println("------------");

	}

	static class dirChange {
		int time;
		char dir;

		dirChange(int time, char dir) {
			this.time = time;
			this.dir = dir;
		}
	}

}

 

 

 

느낀점

• 뱀의 위치를 큐에 넣는 방식은 이후에도 잘 쓸 것 같다!