[골드4] 3190. 뱀 (Java)

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

3190번: 뱀

BAAAAAAAAAMMMMMMMMMMM

---

※  문제를 요약하면 아래와 같습니다.

▶ DUMMY 라는 뱀이 나와서 기어다니는 도스 게임 존재

▶ 사과를 먹으면 뱀 길이가 늘어나며 뱀이 본인 몸이나 벽에 부딪히면 끝

▶ 뱀은 매 초마다 방향을 가지고 이동 하며 다음 과 같은 규칙이 존재

     1. 뱀은 몸길이를 늘려 머리를  다음칸에 위치

     2. 만약 벽이나 자기 자신의 몸과 부딪히면 게임 종료

     3. 머리가 이동한 칸에 사과가 있지 않으면 꼬리에 있던 칸은 없어짐 == 뱀 길이가 그대로

     4. 머리가 이동한 칸에 사과가 있으면, 사과를 지우고 꼬리에 있던 칸은 없어지지 않음 == 뱀 길이 + 1

▶ Input : 첫째 줄에 보드의 크기 N, 다음 줄에 사과의 개수 K 입력, 이후 K 줄에 사과의 좌표가 행, 열 순으로 입력

                 다음 줄에 뱀의 방향 변환 횟수 L 입력, 이후 L개의 줄에 정수 X와 문자 C 입력

                 (X,C => X초가 끝난 후에 C == L 이면 왼쪽으로 90도 회전, C == R 이면 오른쪽으로 90도 회전)

▶ Output : 첫째 줄에 게임이 몇 초에 끝나는지 출력

---

◈ Input - 1

6
3
3 4
2 5
5 3
3
3 D
15 L
17 D

◈ Output - 1

6
3
3 4
2 5
5 3
3
3 D
15 L
17 D

◈ Input - 2

10
4
1 2
1 3
1 4
1 5
4
8 D
10 D
11 D
13 L

◈ Output - 2

21

◈ Input - 3

10
5
1 5
1 3
1 2
1 6
1 7
4
8 D
10 D
11 D
13 L

◈ Output - 3

13

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 뱀의 행,열 좌표를 저장하기 위한 Snake 클래스, 시간 별 바뀌는 방향 정보를 저장한 SnakeInform 클래스 생성

▶ 뱀의 길이 및 이동 상태를 나타내기 위해 Deque 자료 구조 활용

▶ 맵에서 뱀을 차지하고 있는 상태를 표현하기 위한 visit 배열 생성

▶ 델타 탐색 방향을 동,남,서,북 값으로 설정, 왼쪽 90도, 오른쪽 90도 방향을 인덱스의 +1, -1로 조정 

▶ Deque 구조에서 맨 앞의 좌표를 조회하여 다음 방향으로 이동 하여 아래 항목들을 체크

     1. 다음 방향에 사과가 없을 경우, Deque 맨 뒤의 좌표를 제거해주고 다음 방향의 좌표를 맨 앞에 추가

     2. 다음 방향에 사과가 있을 경우, 사과칸의 값을 0으로 바꾼 후, Deque 다음 방향의 좌표를 맨 앞에 추가

     3. 체크한 턴에 시간초 + 1

▶ visit 배열이 true 이거나, 인덱스 범위 밖이면 종료

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

class Snake {
	int m_nRow;
	int m_nCol;
	public Snake() {
		// TODO Auto-generated constructor stub
	}

	public Snake(int m_nRow, int m_nCol) {
		super();
		this.m_nRow = m_nRow;
		this.m_nCol = m_nCol;
	}
}

class SnakeInform {
	int m_nTime;
	char m_chDirection;
	
	public SnakeInform() {
		// TODO Auto-generated constructor stub
	}
	
	public SnakeInform(int m_nTime, char m_chDirection) {
		super();
		this.m_nTime = m_nTime;
		this.m_chDirection = m_chDirection;
	}
}


public class Main {

	static int N, K, L, nDirection;
	static int[][] narrMap;
	
	final static int APPLE = 2;
	
	// 동,남,서,북
	static int[] dr = {0, 1, 0, -1};
	static int[] dc = {1, 0, -1, 0};
	
	public static void main(String[] args) throws NumberFormatException, IOException {

		// TODO Auto-generated method stub
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));
	
		N = Integer.parseInt(bReader.readLine());
		narrMap = new int[N][N];
		
		K = Integer.parseInt(bReader.readLine());
		
		// 사과 위치 입력 받구
		for(int i = 0; i < K; i++) {
			StringTokenizer st = new StringTokenizer(bReader.readLine());
			int nAppleRow = Integer.parseInt(st.nextToken())-1;
			int nAppleCol = Integer.parseInt(st.nextToken())-1;
		
			narrMap[nAppleRow][nAppleCol] = APPLE;
		}
		
		
		L = Integer.parseInt(bReader.readLine());
		SnakeInform[] info = new SnakeInform[L];
		// 뱀의 움직임에 대한 정보 입력 받자
		for(int i = 0; i < L; i++) {
			StringTokenizer st = new StringTokenizer(bReader.readLine());
			
			int nTime = Integer.parseInt(st.nextToken());
			char chDirection = st.nextToken().charAt(0);
			
			info[i] = new SnakeInform(nTime, chDirection);
		}
		
		// 뱀과 시간의 초기 상태 설정
		Snake snake = new Snake();
		int nTime = 0;
		int nTimeIndex = 0;
		int nDirection = 0;
		
		// 뱀의 몸 상태 나타내는 boolean!
		boolean[][] barrSnake = new boolean[N][N];
		barrSnake[0][0] = true;
		
		Deque<Snake> queueSnake = new LinkedList<>();
		queueSnake.add(snake);
		
		// 벽에 부딪히거나 자신의 몸과 부딪히면 끝이 나
		while(!queueSnake.isEmpty()) {
			Snake snakeTemp = queueSnake.getFirst();
			
			// 뱀이 n초뒤에 방향 d를 바꾼다아
			if(nTimeIndex < L 
					&& nTime == info[nTimeIndex].m_nTime) {
				// 동 남 서 북 으로 델타 방향 설정하여 90도 관계 성립!
				if(info[nTimeIndex].m_chDirection == 'L')
					nDirection--;
				if(info[nTimeIndex].m_chDirection == 'D')
					nDirection++;
				
				// 동 남 서 북 델타 사이즈에 맞추어 변경
				if(nDirection > 3)
					nDirection = 0;
				if(nDirection < 0 )
					nDirection = 3;
				
				nTimeIndex++;
			}

			nTime++;
			
			int nSearchRow = snakeTemp.m_nRow + dr[nDirection];
			int nSearchCol = snakeTemp.m_nCol + dc[nDirection];
			
			// 벽이나 지 몸에 충돌하였다아
			if( nSearchRow < 0 || nSearchCol < 0 || nSearchRow >= N || nSearchCol >= N ||
					barrSnake[nSearchRow][nSearchCol])
				break;
			else {
				barrSnake[nSearchRow][nSearchCol]= true;
				
				queueSnake.addFirst(new Snake(nSearchRow, nSearchCol));
				// 사과가 있을 때는 제거 안한다.
				// 없을 때는 꼬리 제거
				if(narrMap[snakeTemp.m_nRow][snakeTemp.m_nCol] != APPLE) {
					Snake tail = queueSnake.pollLast();
					// 뱀의 몸이 더이상 아닌 배열 공간은 false로!
					barrSnake[tail.m_nRow][tail.m_nCol] = false;
				} else
					narrMap[snakeTemp.m_nRow][snakeTemp.m_nCol] = 0;
			}
				
			//nTime++;
		}
		
		bWriter.write(String.valueOf(nTime));
		bWriter.close();
	}
	
}

---

Good Luck! (피드백 감사합니다!)