백준 3190번 : 뱀

 문제

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

3190번: 뱀

3190 뱀

 

 구현 방법

투 포인터 처럼 뱀의 제일 앞 부분, 뱀의 제일 뒷 부분을 큐에 넣고 반복문을 돌려주었습니다.
위 예제는 문제의 예제2번의 과정을 그렸습니다.

 

반복문 동작 순서

1. 뱀의 앞이고 해당 초수에 뱀의 방향 정보가 존재할 때 방향을 바꿔준다.
2. 바뀐 방향을 맵에 넣어준다.
3. 뱀의 꼬리이고 해당 위치에 방향 값이 존재할 때 방향을 바꿔준 후 맵에 있는 방향 값을 없애준다.
4. 이동 위치를 탐색한다.
5. 뱀의 앞이고 이동 위치가 맵 범위를 벗어나거나 뱀의 일부분이면 반복문을 끝내준 후 초수를 출력한다.
6. 뱀의 앞 일 때, 이동 위치 맵에 사과가 있다면 flag = true
7. 이동하고 큐에 다시 값을 넣어준다.
8. 뱀의 꼬리 일 때, 사과가 없었다면 꼬리를 이동해주고 사과가 있었다면 꼬리가 움직이지 않기 때문에 그대로 값을 넣어준다.

뱀의 앞쪽에서 방향 정보가 바꼈을 때 맵에 저장해 주는 이유는 꼬리에서도 해당 위치에서 방향 전환을 하기 위해서입니다.

따라서 맵에 방향을 넣어주고 꼬리가 해당 위치에 도달해서 방향을 바꿔주면 맵에 있는 방향은 없애주어야 합니다.

 

 구현 코드

package BOJ.Gold;

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

public class BOJ3190_뱀 {
	static int N, cnt;
	static boolean flag;
	static int[][] map, deltas = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 우 하 좌 상 
	static Map<Integer, Character> snakeDir;
	static Queue<Move> queue;
	static class Move {
		int r, c, dir;
		boolean tail;

		public Move(int r, int c, int dir, boolean tail) {
			super();
			this.r = r;
			this.c = c;
			this.dir = dir;
			this.tail = tail;
		}
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		map[0][0] = 1; // 뱀
		queue = new LinkedList<>();
		queue.offer(new Move(0, 0, 0, false)); // 뱀 앞
		queue.offer(new Move(0, 0, 0, true)); // 뱀 뒤
		int K = Integer.parseInt(br.readLine());
		StringTokenizer st = null;
		for (int k=0;k<K;k++) {
			st = new StringTokenizer(br.readLine());
			map[Integer.parseInt(st.nextToken())-1][Integer.parseInt(st.nextToken())-1] = 2; // 사과
		}
		snakeDir = new HashMap<>(); // 뱀의 방향 변환 정보
		int L = Integer.parseInt(br.readLine());
		for (int l=0;l<L;l++) {
			st = new StringTokenizer(br.readLine());
			snakeDir.put(Integer.parseInt(st.nextToken()), st.nextToken().charAt(0));
		}
		System.out.println(snakeMove());
	}
	
	static int snakeMove() {
		while(!queue.isEmpty()) {
			flag = false;
			for (int s=0;s<2;s++) {
				Move now = queue.poll();
				
				if(snakeDir.containsKey(cnt) && !now.tail) { // 뱀의 앞이고 cnt초에 해당하는 뱀의 방향 정보가 존재할 때
					if (snakeDir.get(cnt)=='L') now.dir = (now.dir+3)%4; // 왼쪽으로 90도
					else now.dir = (now.dir+1)%4; // 오른쪽으로 90도
					map[now.r][now.c] = -(now.dir+1); // 맵에 방향 값 넣어주기
				}
				
				if (now.tail && map[now.r][now.c]<0) { // 뱀의 꼬리이고 방향 값이 존재할 때
					now.dir = -(map[now.r][now.c]+1); // 해당 방향으로 바꿔주고
					map[now.r][now.c] = 0; // 맵에 있는 방향 값 없애주기
				}
				
				int nr = now.r+deltas[now.dir][0];
				int nc = now.c+deltas[now.dir][1];
				
				if (!now.tail && (!isIn(nr, nc) || map[nr][nc]==1)) return cnt+1; // 뱀의 앞이고 범위를 벗어나거나 뱀의 일부분일 때 끝 
				
				if (!now.tail) { // 뱀의 앞 일 때
					if (map[nr][nc]==2) flag = true; // 사과라면 flag는 true
					map[nr][nc] = 1; 
					queue.offer(new Move(nr, nc, now.dir, now.tail));
				} else {
					if (!flag) { // 사과가 없었다면 꼬리 이동
						map[now.r][now.c] = 0; // 원래 꼬리 지워주고
						queue.offer(new Move(nr, nc, now.dir, now.tail)); // 새로운 꼬리 추가
					} else queue.offer(now); // 사과가 있었다면 꼬리는 움직이지 않기 때문에 그대로 값을 넣어줌
				}
			}
			cnt++;
		}
		return 0;
	}
	
	static boolean isIn(int nr, int nc) {
		return nr>=0 && nr<N && nc>=0 && nc<N;
	}
}

 

정답!