자바(백준) 3190 뱀

오답 노트 & 새로 알게 된 점

뱀 문제를 읽자마자 Deque가 떠올랐다.

 

시뮬레이션은 문제를 정말 잘 읽고 요약하는 습관이 필요한 것 같다. 

요약하면서 어떻게 구현하면 좋을지 생각을 같이 하는 연습이 필요하다.

 

문제는 아래와 같이 정리하면 된다.

끝날 경우 2번을 보면 자기 자신과 몸이 부딪힐 경우이다.

이 때는 현재 머리를 놓은 위치를 dq의 element들과 비교해주면 된다.

 

 

 

order 배열은 시간에 따라 방향이 바뀌는 값을 저장한다.

D는 +1, L은 -1로 생각하여 order 배열에 넣어준다.

방향은 아래의 사진과 같이 생각하면 된다.

사진과 맞춰 dx, dy 배열도 방향 설정을 해주어야한다.

 

---

코드

 

import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N, K, L, ans;
    static int dx[] = {0, 1, 0, -1};
    static int dy[] = {1, 0, -1, 0};
    //->방향이 0부터 시계방향으로 1, 2, 3
    static boolean apple[][];
    static int order[];
    public static void main(String[] args) throws IOException {
        input();
        pro();
 
        System.out.println(ans+1);
    }
 
    static void pro() {
        Deque<Info> dq = new ArrayDeque<>();
        dq.offer(new Info(0, 0, 0));
 
        while (!dq.isEmpty()) {
            Info info = dq.peekFirst();
 
            if(order[ans] == 1){
                info.status = (info.status + 1) % 4;
            }
            else if(order[ans] == -1){
                info.status = (info.status - 1 + 4) % 4;
            }
 
            int nextX = info.x + dx[info.status];
            int nextY = info.y + dy[info.status];
 
            if(!isRangeTrue(nextX, nextY)) return;
            if(isContain(dq, nextX, nextY)) return;
 
            dq.offerFirst(new Info(nextX, nextY, info.status));
            ans++;
 
            if(apple[nextX][nextY]){
                apple[nextX][nextY] = false;
            }
            else{
                dq.pollLast();
            }
        }
    }
 
    static boolean isContain(Deque<Info> dq, int x, int y) {
        for (Info info : dq) {
            if(info.x == x && info.y == y) return true;
        }
        return false;
    }
 
    static boolean isRangeTrue(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < N;
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        N = atoi(br.readLine());
 
        K = atoi(br.readLine());
 
        apple = new boolean[N][N];
 
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int x = atoi(st.nextToken());
            int y = atoi(st.nextToken());
            apple[x-1][y-1] = true;
            //문제에서 1,1 부터 시작한다
            //나는 0,0 부터 시작이기 때문에 사과의 좌표를 하나씩 땅겨줘야한다.
        }
 
        L = atoi(br.readLine());
        order = new int[10001];
 
        for (int i = 0; i < L; i++) {
            st = new StringTokenizer(br.readLine());
            int time = atoi(st.nextToken());
            String dir = st.nextToken();
 
            switch (dir){
                case "D":
                    order[time] = 1;
                    break;
                case "L":
                    order[time] = -1;
                    break;
            }
        }
 
    }
 
 
 
    static class Info{
        int x, y, status;
 
        public Info(int x, int y, int status) {
            this.x = x;
            this.y = y;
            this.status = status;
        }
    }
}