[JAVA] 백준 3190번 : 뱀 (삼성 SW 역량 테스트 기출 문제)

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

3190번: 뱀

문제

 

해결 방안

문제 전체 다 꼼꼼히 읽어봐야하는 Simulation(구현) 문제이다.

먼저 크게 1. 전체 입력 받는 부분 2. 게임 돌아가는 부분 두 가지로 나누어서 생각을 해봤다.

1. 전체 입력 받는 부분

1-1 보드의 크기
사과의 위치가 행, 열 그대로 주어져서 N+1 x N+1로 설정하였다.

1-2 사과의 위치
보드 위치 위에 사과가 있는 경우 1을 저장해주었다. (board[row][col] = 1)

1-3 뱀의 방향 정보
HashMap 자료구조를 이용하여 key에 시간을 넣어주고 value에 방향값을 넣어줘서 나중에 key값이 있는지 쉽게 찾을 수 있게 하였다.

2. 뱀 게임이 돌아가는 부분

시간에 따른 반복문을 돌게 하였다. 즉 while 안은 1초동안 이뤄지는 일들이다.
index 값을 이용하여 뱀의 머리가 진행할 방향을 설정해주었다.
초깃값은 index=0으로 오른쪽 방향이다.(dx[0], dy[0])
index=0 오른쪽 // index=1 아래 // index=2 왼쪽 //index=3 위
2-5에서 오른쪽으로 방향을 틀면 index++ 이고 왼쪽으로 방향을 틀면 index--가 될것이다.

2-1 다음 움직임 설정
nx, ny를 이용하여 현재 위치에 머리가 진행할 방향으로 이동해준다.
nx = cx + dx[index]
ny = cy + dy[index]

2-2 다음 움직임에 따른 게임이 끝나는지 확인
2-2-1 nx, ny가 벽에 부딪히는 경우(범위 넘어가는 경우)를 확인해준다.
2-2-2 nx, ny가 자기 몸통에 부딪힌 경우를 확인해준다.(snake 몸통 정보 확인)

2-3 보드에 사과 유무에 따른 일 수행
2-3-1 사과 있을 때 머리만 늘어난다.
2-3-2 사과 없을 때 머리는 늘어나고 꼬리는 줄어든다.

2-4 현재 움직임에 다음 움직임 저장

2-5 뱀의 방향 이동 정보가 있는지 확인하고 있으면 방향 설정
해당 시간이 HashMap key값에 있는지 확인하고 방향을 새로 설정해준다. 

 

자세한 것은 코드 주석과 비교하며 코드를 참고하면 된다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

// 뱀
// NxN 정사각형 보드
// 맨위 맨 위측 위치(1,1), 처음 오른쪽 방향을 향함
// 뱀은 계속 머리쪽이 늘어남
// 사과 있으면 사과 없어지고 머리 늘려서 꼬리 그대로
// 사과 없으면 머리 늘려서 꼬리가 위치한 칸 비워줌
public class Main {

	static int n; // 보드의 크기 (2~100)
	static int k; // 사과의 갯수 (0~100)
	static int l; // 뱀의 방향 변환 횟수 (1~100)
	static int time; // 게임 시간
	static int[][] board;
	
	static List<int[]> snake; //뱀의 몸통 위치 (x,y)
	
	// 처음 시작은 오른쪽 방향을 보고 있음
	// 0:오른쪽   1:아래쪽   2:왼쪽   3:위
	// D(오른쪽)가 다오면 index++
	// L(왼쪽)이 나오면 index--
	static int index = 0;
	static int[] dx = {0, 1, 0, -1}; //세로
	static int[] dy = {1, 0, -1, 0}; //가로
	
	static Map<Integer, String> dir; // 뱀의 방향 정보
	
	public static void main(String[] args) throws Exception, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		n = Integer.parseInt(br.readLine());
		k = Integer.parseInt(br.readLine());
		
		// 1,1이 맨 위 맨 좌측
		board = new int[n+1][n+1];
		
		// 사과 위치 입력
		String str;
		int row; // 행
		int col; // 열
		for(int i=0; i<k; i++) {
			str = br.readLine();
			
			row = Integer.parseInt(str.split(" ")[0]);
			col = Integer.parseInt(str.split(" ")[1]);
			
			board[row][col] = 1;
		}
		
		// 뱀 방향 정보 입력
		dir = new HashMap<>();
		l = Integer.parseInt(br.readLine());
		for(int i=0; i<l; i++) {
			str = br.readLine();
			int timeInfo = Integer.parseInt(str.split(" ")[0]);
			String directionInfo = str.split(" ")[1];
			
			dir.put(timeInfo, directionInfo);
		}
		
		// 뱀 시작 지점 (1,1) (x,y)
		snake = new LinkedList<>();
		snake.add(new int[]{1,1});
		
		time = 0;
		int nx, ny; // 다음 움직임
		int cx, cy; // 현재 움직임(1,1)
		cx = 1;
		cy = 1;
		// 뱀 움직임 시작
		while(true) {
			time++;
			
			// 다음 움직임(머리 데이터)
			nx = cx + dx[index];
			ny = cy + dy[index];
			
			// 끝나는지 확인
			if(isFinish(nx,ny)) break;
			
			// 사과 있는지 확인
			// 사과 있으면 사과 없어지고 머리 늘려서 꼬리 그대로
			if(board[nx][ny] == 1) {
				board[nx][ny] = 0;
				snake.add(new int[] {nx,ny}); // 머리 정보 추가
			}
			// 사과 없으면 머리 늘려서 꼬리가 위치한 칸 비워줌
			else {
				snake.add(new int[] {nx,ny}); // 머리 정보 추가
				snake.remove(0); // 꼬리 index는 0
			}
			 
			cx = nx;
			cy = ny;
			
			// 해당 시간 끝났을 때 다음 방향 정해주기
			if(dir.containsKey(time)) {
				// D(오른쪽)가 다오면 index++
				if(dir.get(time).equals("D")) {
					index++;
					if(index == 4)
						index = 0;
				}
				// L(왼쪽)이 나오면 index--				
				if(dir.get(time).equals("L")) {
					index--;
					if(index == -1)
						index = 3;
				}
				
			}
		}
		
		System.out.println(time);
	}
	
	// 게임이 끝나는지 확인
	static boolean isFinish(int nx, int ny){
		
		// 벽에 부딪히거나
		if(nx<1 || ny<1 || nx>=n+1 || ny>=n+1) 
			return true;
		
		// 자기 몸통에 닿거나
		for(int i=0; i<snake.size(); i++) {
			if(nx == snake.get(i)[0] && ny == snake.get(i)[1]) 
				return true;
		}
		
		return false;
	}

}