[백준 3190, Java] 뱀

문제

www.acmicpc.net/problem/3190

3190번: 뱀

 

처음풀이

 맨 처음에는 head와 tail 만 생각하고 풀었다. head가 빈칸을 만났을 때 내부에서 다시 for문을 돈 이유는 tail을 지운 후 원래있던 tail 이전의 칸을 tail 로 업데이트 하기 위해서 였다. 그런데 이 로직은  

 

E S S E

E S(꼬리) S E

 

의 경우 (뱀이 →→↑← 의 방향으로 이동한 경우) head를 tail 로 업데이트 하게 된다. (E: 빈칸, S: 뱀)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int K;
    static int L;

    static int[][] map;
    static final int EMPTY = 0;
    static final int SNAKE = -1;
    static final int APPLE = 1;
    static HashMap<Integer,String> hashMap;

    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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        K = Integer.parseInt(br.readLine());

        map = new int[N][N];
        for(int k=0; k<K; k++){
            st = new StringTokenizer(br.readLine()," ");
            int x = Integer.parseInt(st.nextToken())-1;
            int y = Integer.parseInt(st.nextToken())-1;
            map[x][y] = APPLE;
        }

        L = Integer.parseInt(br.readLine());
        hashMap = new HashMap<>();
        for(int l=0;l<L;l++){
            st = new StringTokenizer(br.readLine()," ");
            int second = Integer.parseInt(st.nextToken());
            String direction = st.nextToken();

            hashMap.put(second, direction);
        }



        int result = getSecond();
        bw.write(String.valueOf(result));
        bw.flush();

    }

    static int getSecond(){
        int second = 0;
        int headX = 0;
        int headY = 0;
        int tailX = 0;
        int tailY = 0;
        int snakeDirection = 1;

        int[][] snakeVisitSecond  = new int[N][N];
        for(int r =0; r<N; r++){
            for(int c=0; c<N; c++){
                snakeVisitSecond[r][c] = N*N;
            }
        }
        map[0][0] =SNAKE;
        snakeVisitSecond[0][0] = 0;

        while(true){
            ++second;

            System.out.println("----------------------");
            System.out.println((second-1)+"초");
            System.out.println("현재 head ("+headX+","+headY+")");
            System.out.println("현재 tail ("+tailX+","+tailY+")");
            printMap();



            //방향변환 확인
            String rotate = hashMap.get(second);
            if(rotate!=null){
                if(rotate.equals("L")){
                    snakeDirection = (snakeDirection-1)<0? 3 : snakeDirection-1;
                }
                else if(rotate.equals("D")){
                    snakeDirection = (snakeDirection+1)>4? 0: snakeDirection+1;
                }
            }

            //이동할 칸 확인
            int nx = headX + dx[snakeDirection];
            int ny = headY + dy[snakeDirection];

            if(nx<0 || ny<0 ||nx>=N ||ny>=N){
                break;
            }
            else if(map[nx][ny] ==SNAKE){
                break;
            }
            else if(map[nx][ny] == APPLE){
                map[nx][ny] = SNAKE;
                snakeVisitSecond[headX][headY] = second;

                headX = nx;
                headY = ny;
            }
            else if(map[nx][ny]==EMPTY){
                map[nx][ny] = SNAKE;
                snakeVisitSecond[headX][headY] = second;

                headX = nx;
                headY = ny;

                map[tailX][tailY] = EMPTY;
                snakeVisitSecond[headX][headY] = N*N;

                int beforeTailX = 0;
                int beforeTailY = 0;
                for(int d =0; d<4; d++){
                    int ntx = tailX + dx[d];
                    int nty = tailY + dy[d];
                    int minSecond = N*N;

                    if(ntx>=0 && ntx<N && nty>=0 && nty<N){
                        if(map[ntx][nty] == SNAKE){
                            if(minSecond> snakeVisitSecond[ntx][nty]){
                                beforeTailX = ntx;
                                beforeTailY = nty;
                            }
                        }
                    }
                }

                tailX = beforeTailX;
                tailY = beforeTailY;

            }
        }

        return second;
    }

    static void printMap(){
        for(int r =0; r<N; r++){
            for(int c=0; c<N; c++){
                System.out.printf("%3d",map[r][c]);
            }
            System.out.println();
        }
    }
}

 

두번째 풀이

 따라서 뱀을 표현하는 방법을 찾아야하는데, 이 풀이에서는 Deque를 이용했다. 그 이유는 head, tail 양방향에서 enqueue, dequeue가 발생했기 때문이다. 

 

실수한 것

"게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전시킨다는 뜻이다" 이기 때문에 마지막에 방향을 업데이트 해줘야 한다

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

class Point{
    int x;
    int y;
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "Point{" +
                "x=" + x +
                ", y=" + y +
                '}';
    }
}
public class Main {
    static int N;
    static int K;
    static int L;
    static int[][] map;
    static final int EMPTY = 0;
    static final int APPLE = 1;
    static final int SNAKE = 2;
    static HashMap<Integer,String> hashMap;
    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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];

        K = Integer.parseInt(br.readLine());
        for(int k=0; k<K; k++){
            st = new StringTokenizer(br.readLine()," ");
            int x = Integer.parseInt(st.nextToken())-1;
            int y = Integer.parseInt(st.nextToken())-1;
            map[x][y] = APPLE;
        }

        L = Integer.parseInt(br.readLine());
        hashMap = new HashMap<>();
        for(int l=0;l<L;l++){
            st = new StringTokenizer(br.readLine()," ");
            int second = Integer.parseInt(st.nextToken());
            String rotate = st.nextToken();
            hashMap.put(second,rotate);
        }

        int result = getFinishTime();
        bw.write(String.valueOf(result));
        bw.flush();
    }
    static int getFinishTime(){
        int second = 0;

        Deque<Point> dequeue =new LinkedList<>();
        dequeue.add(new Point(0,0));
        map[0][0] = SNAKE;
        int direction = 1;
        while(true){
            ++second;

            //현재 뱀의 머리에서 다음 칸 확인
            Point currentHead = dequeue.peek();
            int nx = currentHead.x + dx[direction];
            int ny = currentHead.y + dy[direction];


            if(nx<0 || ny<0 || nx>N-1 || ny>N-1){
                break;
            }
            else if(map[nx][ny] == SNAKE){
                break;
            }
            else if(map[nx][ny] == APPLE){
                map[nx][ny] = SNAKE;
                dequeue.addFirst(new Point(nx,ny));
            }
            else if(map[nx][ny] == EMPTY){
                map[nx][ny] = SNAKE;
                dequeue.addFirst(new Point(nx,ny));

                Point tail =dequeue.removeLast();
                map[tail.x][tail.y] = EMPTY;
            }


            // 방향 바뀌는지 확인
            String rotate = hashMap.get(second);
            if(rotate!=null){
                if(rotate.equals("L")){
                    direction = direction-1 <0 ? 3 : direction-1;
                }
                else{
                    direction = direction+1 >3? 0 : direction+1;
                }
            }
        }


        return second;
    }

    static String getDirection(int d){
        switch (d){
            case 1 :
                return "동";
            case 2:
                return "남";
            case 3:
                return "서";
            case 0:
                return "북";
        }
        return "no";
    }

    static void printMap(){
        for(int r= 0; r<N; r++){
            for(int c=0; c<N; c++){
                System.out.printf("%2d",map[r][c]);
            }
            System.out.println();
        }
    }
}