BOJ - 뱀 3190번 (JAVA)

❓ 문제 - 백준 뱀 3190번 - JAVA 풀이법

출처 

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

3190번: 뱀

 

📝 문제해결법

1. 이 문제는 Queue + 구현 + 해시맵으로 풀었다.

• map이라는 2차원 배열로 처음 입력받은 사과의 정보를 1로 넣는다.
• 방향 전환에 대한 정보를 해쉬맵에 key값을 time, value L or D로 넣어 뱀을 움직이면서 현재 시간에 해당하는 key 값이 존재하면 해당 방향으로 방향전환 하도록 구현하였다.
• 뱀에 대한 정보를 queue에 넣어서 관리한다. 뱀은 map에 2라는 값으로 저장해둔다.
• 만약 뱀을 이동시켰을 때 종료되는 조건인지 확인한다. -> 벽에 닿았는지 ? 자기 자신과 닿았는지?
• 만약 조건에 해당하지 않으면 이동가능 하므로 사과가 있는지 체크하고 만약 사과가 있으면 사과를 먹고, 만약 사과가 없으면 기존 꼬리 부분에 존재했던 뱀을 없애야 하므로 queue에서 pop하고 해당 map의 부분을 0으로 변경한다.
• 그리고 현재 뱀의 머리가 가르키는 부분을 queue에 다시 넣어주고 해당 map의 부분을 2로 변경한다.
• 현재 시간에 변경해야할 방향이 있으면 해쉬맵으로 체크한다. 
• dx, dy를 동 -> 남 -> 서 -> 북으로 구성하면 L일 때는 방향을 왼쪽으로 한칸씩 밀고, R일 때는 방향을 오른쪽으로 한칸씩 밀면 해당 방향에 맞춰 90도 회전이 가능하다.

2. 느낀점

• 예전에 파이썬으로 풀이하여 포스팅을 해서 다시 포스팅하기 머쓱하지만... 자바니깐 ^^..
• 그래도 지난 번엔 해쉬맵을 사용하지 않아서 메모리가 125600 KB 사용했는데 -> 현재 해쉬맵 + 자바 구현으로 14796 KB로 확 줄었다.... 
• 오늘도 성장했다 ^_^...

 

💻 소스코드

// BOJ - 뱀(3190번)
// 시뮬레이션 + 큐

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class Main_3190 {

	public static class Node {
		int x;
		int y;
		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	public static int[] dx = {0, 1, 0, -1};
	public static int[] dy = {1, 0, -1, 0};
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		HashMap<Integer, String> change = new HashMap<Integer, String>();
		int n = Integer.parseInt(br.readLine());
		int k = Integer.parseInt(br.readLine());
		int[][] map = new int[n+1][n+1];
		for(int i=0;i<k;i++) {
			String[] data = br.readLine().split(" ");
			int r = Integer.parseInt(data[0]);
			int c = Integer.parseInt(data[1]);
			map[r][c] = 1;
		}
		
		int l = Integer.parseInt(br.readLine());
		for(int i=0;i<l;i++) {
			String[] data = br.readLine().split(" ");
			change.put(Integer.parseInt(data[0]), data[1]);
		}
		
		int time = 0;
		int nx = 1;
		int ny = 1;
		int dir = 0;
		Queue<Node> snack = new LinkedList<>();
		snack.offer(new Node(nx, ny));
		map[1][1] = 2; // 뱀 표시
		
		while(true) {
			time++;
			nx += dx[dir];
			ny += dy[dir];
			if(nx < 1 || nx > n || ny < 1 || ny > n || map[nx][ny] == 2) {
				break;
			}
			// 사과 유무
			if(map[nx][ny] == 1) {
				map[nx][ny] = 0;
			} else {
				Node tail = snack.poll();
				map[tail.x][tail.y] = 0;
			}
			snack.add(new Node(nx, ny));
			map[nx][ny] = 2;
			
			if(change.containsKey(time)) {
				String change_dir = change.get(time);
				if(change_dir.equals("L")) {
					dir = (dir==0?3:dir-1);
				} else {
					dir = (dir==3?0:dir+1);
				}
			}
			
		}
		
		System.out.println(time);

	}

}