[백준 / BOJ] 3190번 : 뱀 (JAVA)

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

3190번: 뱀

삼성 코테 기출문제 풀기 : 백준 [2/45], 코드트리 [0/12]

 

뱀의 몸 위치 확인하기

뱀의 몸 위치를 확인하는 것은 두 가지에서 필요하다.

 

1. 머리와 꼬리의 위치를 알아야 움직임에 따라 새 머리를 넣고, 꼬리를 빼줄 수 있다.

2. 몸통의 위치를 알아야 머리가 몸통과 부딪혔는지 알 수 있다.

 

따라서 머리, 꼬리의 위치 뿐 아니라 머리부터 꼬리까지 몸통 전체의 위치를 파악해야 한다. 머리와 꼬리를 수정하기 쉽도록 Deque로 구현하였고, 뱀의 전체 몸은 body라는 2차원 배열에 1을 찍어서 확인했다.

 

즉, 뱀이 움직이는 건 다음과 같다.

int[] head = snake.peekFirst(); // Deque의 가장 앞은 머리
int[] tail = snake.peekLast(); // Deque의 가장 뒤는 꼬리

// 머리가 이동할 위치
int nr = head[0] + dr[D];
int nc = head[1] + dc[D];

// 이동할 곳이 벽을 넘어가려 하거나, 몸통이 있는 곳이면 아웃
if(nr >= N || nc >= N || nr < 0 || nc < 0 || body[nr][nc] == 1) {
    break;
}

if(map[nr][nc] == 1) { // 이동하는 곳에 사과가 있는 경우
    body[nr][nc] = 1; // 새 머리를 body에 표시
    snake.addFirst(new int[] {nr, nc}); // 새 머리를 Deque에 추가
    map[nr][nc] = 0; // 사과 없앰
} else {
    body[nr][nc] = 1; // 새 머리를 body에 표시
    body[tail[0]][tail[1]] = 0; // 꼬리를 body에서 제거
    snake.addFirst(new int[] {nr, nc}); // 새 머리를 Deque에 추가
    snake.pollLast(); // 꼬리를 Deque에서 제거
}

 

뱀 방향 바꾸기

지정된 시간마다 뱀은 방향을 바꾸어야 한다. 이 때 명령은 다 잘 듣는데 정답을 맞추는 데에 애를 먹었는데, 제시문에 "게임 시작 시간으로부터 X초가 끝난 뒤에" 라는 말이 있는 것을 놓쳤기 때문이다. X초가 되자마자가 아니라, X초에 움직인 다음에 방향을 변경해주는 것이다. 원래 코드에는 뱀이 움직이는 것보다 방향 D를 바꾸는 것이 먼저 나왔다. 이 때문에 계속 시간이 다르게 나왔고,

 

시간 증가 -> 뱀 움직임 -> 시간이 X인 경우 방향 변경

 

로 순서를 바꾸자 정답처리 되었다.

 

전체 코드

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		int K = Integer.parseInt(br.readLine());
		
		int[][] map = new int[N][N];
		int[][] body = new int[N][N];
		
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken()) - 1;
			int c = Integer.parseInt(st.nextToken()) - 1;
			map[r][c] = 1;
		}
		
		int L = Integer.parseInt(br.readLine());
		int[][] op = new int[L][2];
		
		for (int i = 0; i < L; i++) {
			st = new StringTokenizer(br.readLine());
			int X = Integer.parseInt(st.nextToken());
			int C = st.nextToken().charAt(0) == 'L' ? 0 : 1;
			op[i][0] = X;
			op[i][1] = C;
		}
		
		int time = 0;
		int pointer = 0;
		Deque<int[]> snake = new LinkedList<>();
		snake.add(new int[] {0, 0});
		body[0][0] = 1;
		
		int D = 3;
		int[] dr = {-1,0,1,0};
		int[] dc = {0,-1,0,1};
		while(true) {
			time++;
			
			int[] head = snake.peekFirst();
			int[] tail = snake.peekLast();
			
			int nr = head[0] + dr[D];
			int nc = head[1] + dc[D];
			
			if(nr >= N || nc >= N || nr < 0 || nc < 0 || body[nr][nc] == 1) {
				break;
			}
			
			if(map[nr][nc] == 1) {
				body[nr][nc] = 1;
				snake.addFirst(new int[] {nr, nc});
				map[nr][nc] = 0;
			} else {
				body[nr][nc] = 1;
				body[tail[0]][tail[1]] = 0;
				snake.addFirst(new int[] {nr, nc});
				snake.pollLast();
			}
            
            int C = -1;
			if(pointer < L && time == op[pointer][0]) {
				C = op[pointer++][1];
			}
			
			if(C == 0) {
				D++;
				if(D == 4) D = 0;
			} else if(C == 1) {
				D--;
				if(D == -1) D = 3;
			}
			
		}
		System.out.println(time);
		
	}

}