[BOJ] 백준 3190 - 뱀 풀이

1. 문제

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

3190번: 뱀

2. 풀이

• static 객체를 2개로 나누어 관리한다
  1. 뱀의 방향 정보를 담고 있는 Move 객체
  2. 뱀이 이동하는 정보를 담고 있는 Snake 객체
• 주요 자료구조
  • Snake head : 머리 이동 객체
  • Snake tail : 꼬리 이동 객체
  • Queue<Move> moveQueue : 뱀의 방향 정보 큐
  • Queue<Snake> dirQueue : 꼬리가 방향 전환하는 정보를 담고 있는 큐
  • boolean[][] visited : 뱀이 방문한지 체크하는 방문 체크 배열
• 입력을 받아 map을 구성하고 방향 정보는 moveQueue에 넣는다. 사과가 있는 곳은 2로 처리한다.
• 그 후 snakeMoveGame() 함수를 실행한다.
  1. 우선 머리를 방향에 맞게 한 칸 이동해서 그곳에 사과가 있는지 파악한다.
  2. 만약 그곳에 사과가 있다면 꼬리를 방향에 맞게 한 칸 움직이고, 그곳을 0으로 만든다.
  3. 그리고 지금 moveQueue에 들어있는 바로 위 객체의 시간이 됬다면, 그 객체를 꺼내어 머리의 방향을 바꾼다.
• 이 로직에서 조심해야 하는 부분은 바로 꼬리의 방향이다.
  • 만약 moveQueue에서 객체를 꺼내어 방향을 바꿨다면, 꼬리는 그 위치에 도달해서는 방금 꺼낸 객체와 같은 방향을 가져야 한다.
  • 예를 들어 3초가 지난 후 (3, 3)에서 D 방향 전환이 나왔다면 그 위치를 dirQueue에 넣고 꼬리를 움직일 때마다 dirQueue의 위치인지 확인해줘야 한다. 
  • 그 위치가 됬다면 dirQueue에서 꺼내어 꼬리 객체의 방향을 바꿔준다.
    
    
    

3. 소스 코드

import java.io.*;
import java.util.*;


public class Main {
    static int N, K, L;
    static int[][] map;
    static int[] dx = {-1, 0, 1, 0};  // 0 : 북 , 1 : 동, 2 : 남 , 3 : 서
    static int[] dy = {0, 1, 0, -1};

    static boolean[][] visited;

    static int result = 0;

    static class Move {
        int time;
        char dirMove;

        public Move(int time, char dirMove) {
            this.time = time;
            this.dirMove = dirMove;
        }
    }

    static class Snake {
        int x;
        int y;
        int dir;

        public Snake(int x, int y, int dir) {
            this.x = x;
            this.y = y;
            this.dir = dir;
        }
    }

    static Snake head;
    static Snake tail;

    static Queue<Move> moveQueue = new ArrayDeque<>();
    static Queue<Snake> dirQueue = new ArrayDeque<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        map = new int[N][N];
        visited = new boolean[N][N];

        for (int i = 0; i < K; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            map[Integer.parseInt(st.nextToken()) - 1][Integer.parseInt(st.nextToken()) - 1] = 2; // 2 : 사과 위치
        }

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

            moveQueue.add(new Move(Integer.parseInt(st.nextToken()) - 1, st.nextToken().charAt(0)));
        }

        head = new Snake(0, 0, 1);
        tail = new Snake(0, 0, 1);

        visited[0][0] = true;

        snakeMoveGame();

        bw.write(Integer.toString(result + 1));
        bw.flush();
        bw.close();
        br.close();
    }

    private static void snakeMoveGame() {
        while (true) {

            if (isAvailable(head.x + dx[head.dir], head.y + dy[head.dir])) {
                head.x += dx[head.dir];
                head.y += dy[head.dir];

                visited[head.x][head.y] = true;

                if (map[head.x][head.y] != 2) {
                    if (!dirQueue.isEmpty() && dirQueue.peek().x == tail.x && dirQueue.peek().y == tail.y) {
                        Snake poll = dirQueue.poll();
                        tail.dir = poll.dir;
                    }

                    visited[tail.x][tail.y] = false;

                    tail.x += dx[tail.dir];
                    tail.y += dy[tail.dir];
                } else {
                    map[head.x][head.y] = 0;
                }
            } else {
                break;
            }

            if (!moveQueue.isEmpty() && moveQueue.peek().time == result) {
                Move poll = moveQueue.poll();
                setDir(poll.dirMove, head);
                dirQueue.add(new Snake(head.x, head.y, head.dir));
            }

            result += 1;
        }
    }

    private static void setDir(char c, Snake s) {
        if (c == 'D') { // 시계방향 90도
            if (s.dir == 3) {
                s.dir = 0;
            } else {
                s.dir += 1;
            }
        } else {        // 반시계방향 90도
            if (s.dir == 0) {
                s.dir = 3;
            } else {
                s.dir -= 1;
            }
        }
    }

    private static boolean isAvailable(int x, int y) {
        if (x >= 0 && x < N && y >= 0 && y < N && !visited[x][y]) {
            return true;
        }
        return false;
    }
}

4. 점수

90/100