[알고리즘] 백준 3190번 뱀 :: 우유

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

 

코드 설명

이중 for문에서 빼낼려고 이상한 짓 하다가 시간을 많이 잡아먹었던 문제였다.

3190번: 뱀

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static Deque<int[]> qu = new LinkedList<>();
    static HashMap<Integer, String> map = new HashMap<>();
    static boolean[][] apple;
    static int[] dy = {0, 1, 0, -1};
    static int[] dx = {1, 0, -1, 0};
    static int N, K, L;
    static int direction = 0;

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

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

        apple = new boolean[101][101];

        // 사과 맵
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());

            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());

            apple[y][x] = true;
        }

        L = Integer.parseInt(br.readLine());

        //
        for (int i = 0; i < L; i++) {
            st = new StringTokenizer(br.readLine());

            int X = Integer.parseInt(st.nextToken());
            String C = st.nextToken();
            map.put(X, C);
        }

        // 이중 포문 break를 사용하지 않기 위한?
        solve();
    }

    private static void solve() {
        int time = 0;

        int curY = 1;
        int curX = 1;

        qu.add(new int[]{1, 1});

        while (true) {
            int ny = curY + dy[direction];
            int nx = curX + dx[direction];

            // 맵 범위에 있는지, 몸통이랑 부딪혔는지 확인
            if (GameoverCheck(ny, nx))
                break;

            time++;

            qu.add(new int[]{ny, nx});

            // 사과가 있으면
            if (apple[ny][nx])
                apple[ny][nx] = false;
                // 사과가 없으면
            else {
                qu.poll();
            }

            if (map.containsKey(time)) {

                if (map.get(time).equals("D")) {
                    direction++;
                    if(direction == 4)
                        direction = 0;
                } else {
                    direction--;
                    if(direction == -1)
                        direction = 3;
                }
            }

            curY = ny;
            curX = nx;
        }
        System.out.println(time + 1);
    }

    private static boolean GameoverCheck(int ny, int nx) {
        boolean flag = false;

        // 범위에 벗어나면
        if (ny < 1 || nx < 1 || N < ny || N < nx)
            flag = true;

        // 몸통에 부딪히면
        for (int[] arr : qu) {

            if (arr[0] == ny && arr[1] == nx) {

                flag = true;
                break;
            }
        }

        return flag;
    }
}