[BaekJoon] 백준 3190번 _ 뱀 for JAVA

 

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

3190번: 뱀

 

 

문제

 

 

---

 

 

재미있는 시뮬레이션 문제였다~!

 

 

그냥 문제 그대로 풀면 된다.

 

 

나는 사과를 set에 넣고 방향을 바꾸는 구간은 map에 넣었다.

 

참고로 set 안에 배열 형태로 넣으면 비교를 못함.

 

예를 들어 set<int[]> 형태로 만들고 set.add(new int[]{}) 이런 형태로 집어넣었다면

 

 

set.contains(new int[]{}) 형태로 비교가 안된다. 배열이니까 주소값이 다르기 때문에...

 

그래서 key를 만들어서 Integer 형태로 넣었다.

 

 

그리고 특이한건 꼬리에 닿아도 멈춰야하기 때문에 몸통을 저장해줘야함.

 

큐를 쓸까 하다가 머리 좌표값도 쓰기 위해 그냥 ArrayList 사용했다.

 

 

 

구현 방법

1. 1초 지남

2. 뱀의 머리 이동시킴

   2-1. 머리가 경계에 닿거나 자기 몸통에 닿으면 끝냄

3. 이동한 칸에 사과가 있는지 확인

   3-1. 사과가 있으면 사과 없앰

   3-2. 사과가 없으면 꼬리가 위치한 칸을 비움

4. 방향을 바꾸는 구간인지 확인

   4-1. 방향을 바꾸는 구간이라면 바꿈 L: 오른쪽, D: 왼쪽

 

 

코드

package BaekJoon;

import java.util.*;
import java.io.*;

public class Main_BJ_3190_뱀 {
	
	static int dx[] = {0,1,0,-1}; // 오른쪽 방향
	static int dy[] = {1,0,-1,0};

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		boolean[][] map = new boolean[N][N]; // 맵에 표시할 것: 뱀의 몸통
		int K = Integer.parseInt(br.readLine());
		Set<Integer> apple = new HashSet<>(); // 사과 위치
		
		StringTokenizer st;
		for(int i=0; i<K; i++) {
			st = new StringTokenizer(br.readLine());
			int key = (Integer.parseInt(st.nextToken())-1) * 1000 + (Integer.parseInt(st.nextToken())-1);
			apple.add(key);
		}
		
		int L = Integer.parseInt(br.readLine());
		Map<Integer, String> turn = new HashMap<>(); // 초:방향
		for(int i=0; i<L; i++) {
			st = new StringTokenizer(br.readLine());
			int num = Integer.parseInt(st.nextToken());
			String dir = st.nextToken();
			
			turn.put(num, dir);
		}
		
		/// 입력 끝 ////
		int answer = 0;
		ArrayList<int[]> snake = new ArrayList<>(); // 뱀 몸통 저장
		snake.add(new int[] {0,0});
		map[0][0] = true;
		int dir = 0; // 오른쪽: (dir+1)%4, 왼쪽: (dir+3)%4
		
		while(true) {
			answer += 1; // 1초 지남
            
			// 1. 몸의 길이를 늘려 머리를 다음칸에 위치시킨다.
			int out[] = snake.get(snake.size()-1);
			// 현재 머리 위치
			int x = out[0];
			int y = out[1];
			
			// 다음 머리 위치
			int nx = x + dx[dir];
			int ny = y + dy[dir];
			if(nx < 0 || nx >= N || ny < 0 || ny >= N || map[nx][ny]) break;
			
			map[nx][ny] = true;
			snake.add(new int[] {nx,ny});
			
			// 2. 이동한 칸에 사과가 있는지 확인한다.
			int key = nx*1000+ny;
			if(!apple.contains(key)) { // 사과가 없는 칸이라면
				// 꼬리가 위치한 칸을 비워준다.
				int outTail[] = snake.get(0);
				// 꼬리가 있는 x,y
				int tx = outTail[0];
				int ty = outTail[1];
				
				map[tx][ty] = false;
				snake.remove(0);
			} else { // 사과가 있는 칸이라면
				apple.remove(key); // 사과 없어짐
			}
			
			// 0. 방향을 바꾸는 구간이라면 방향을 바꾼다.
			if(turn.containsKey(answer)) {
				String d = turn.get(answer);
				if(d.equals("L")) dir = (dir+3)%4;
				else dir = (dir+1)%4;
			}
			
		} // while문 끝
		
		System.out.println(answer);

	}

}

 

 

성능

 

 

 

 

사과 먹고 remove 안해줘서 23%에서 한번 틀렸다. 슬픔

 

문제 제대로 읽자.....제발..........