백준 3190 뱀 [JAVA]

 

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

문제

'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

 

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

 

접근 방법

해당 문제는 뱀이 이차원 배열을 방향에 따라 움직이는 구현문제이다.

구현 문제는 처음에는 어려워보이지만 차근차근해나가보면 답에 도달할 수 있다.

 

우선 스스로 그림을 그려보자!  그러면 구현해야할 목록들이 보일것이다.

1.   뱀의 이동 경로 정하기 (방향전환 구현)
2.   범위를 벗어나거나, 뱀 몸통을 만날때 종료
3.   사과가 있을때 사과을 없애주기, 있는 경우  꼬리 부분 자르기 (뱀의 몸통을 기억해야하므로 Queue 를 이용해 넣어주었다)

 

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

// 구현
// 회전정하기
// 뱀의 몸통 움직이기
public class Main {
    static int[][] arr;
    static int[] dx = {-1, 0, 1, 0}; // 동서남북
    static int[] dy = {0, +1, 0, -1};

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        arr = new int[n+1][n+1];
        int apple = Integer.parseInt(br.readLine());
        for(int i=0; i<apple; i++){
            String[] s = br.readLine().split(" ");
            int x = Integer.parseInt(s[0]);
            int y = Integer.parseInt(s[1]);
            arr[x][y] = 1;
        }

        int l = Integer.parseInt(br.readLine());
        int[] seconds = new int[10001];
        int[] dr = new int[10001];
        for(int i=0; i<l; i++){
            String[] s = br.readLine().split(" ");
            int sec = Integer.parseInt(s[0]);
            seconds[sec] = 1;
            if(s[1].equals("L")){
                dr[sec] = -1;
            }else {
                dr[sec] = +1;
            }
        }

        int curX = 1;
        int curY = 1;
        int curD = 1; // 처음 시작 방향 : 동쪽
        int time = 0;
        // 뱀의 몸통 좌표
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{1,1});
        arr[curX][curY]= 3;
        while(true){
           if(seconds[time] == 1){
               if(dr[time] == -1){ // 왼쪽 회전
                   curD = ((curD -1 + 4) % 4) ;
               } else { // 오른쪽 회전
                   curD = ((curD +1) % 4);
               }
           }
           int nextX = curX + dx[curD];
           int nextY = curY + dy[curD];
           time++;

           // 탈출조건 - 벽에 부딪침.
           if(nextX <=0 || nextX >n || nextY <=0 || nextY >n ){
               break;
           }
           //  자신의 몸에 부딪침
           if(arr[nextX][nextY] == 3){
               break;
           }

           if(arr[nextX][nextY] != 1) { // 사과가 아닐때 - 꼬리 부분 지워주기
               if (!queue.isEmpty()) {
                   int[] tail = queue.poll();
                   arr[tail[0]][tail[1]] = 0;
               }
           }
           queue.add(new int[]{nextX, nextY});
            arr[nextX][nextY] = 3;
           curX = nextX;
           curY = nextY;
       }
        System.out.println(time);
    }
}