[BOJ 3190] 뱀 (Java, BFS, 구현)

 

---

문제 링크 

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

3190번: 뱀

---

풀이

- 주어진 조건에 맞게 BFS, 시뮬레이터 구현 하는 문제

- Queue를 활용하여 뱀의 위치 정보를 관리하고, 맵 데이터를 갱신 시켜 줌

 

게임 조건

게임은 N * N 보드 위에서 진행되고, 게임이 시작할 때 뱀은 맨위 맨 좌측에 위치하고 뱀의 길이는 1이다.
뱀은 맨 처음 오른쪽으로 향한다.

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

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 구한다

 

방향 전환*(실수 포인트)

- 방향 전환 정보는 class를 정의하고 LinkedList에 담아서 정해진 시간에 방향 전환하도록 함

 

이동할 때

- Queue 의 선입선출(FIFO) 성질을 활용하여 뱀의 위치 정보를 관리할 수 있도록 함

- int[][] GAME_MAP에 뱀(2)에 대한 정보 표시

 

Queue 에 뱀의 시작 위치 기록

( 1, 1 )

 

GAME_MAP (0 : 빈 필드, 1 : 사과, 2 : 뱀)

~< (2)	0 또는 1
0	0

 

1) 사과(1)가 없는 경우 

- 오른쪽으로 한칸 이동

- Queue에서 이전 위치 정보(1, 1)를 꺼내서 0으로 갱신

0	~< (2)
0	0

- Queue에 이동한 뱀의 현재 위치 정보를 입력 

( 1, 2 )

 

2) 사과(1)가 있는 경우

- 오른쪽으로 한칸 이동

- 사과(1)가  있기 때문에 뱀의 길이가 증가

~ (2)	~< (2)
0	0

- Queue에 이동한 뱀의 위치 정보를 입력 

( 1, 1 ), ( 1, 2 )

 

 

예제 입력 1

 

예제 입력 2

 

예제 입력 3

---

제출 코드

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

public class Main {
     private static StringBuilder sb = new StringBuilder();
    private static InputProcessor inputProcessor = new InputProcessor();

    public static void main(String[] args) {
        input();
        pro();
        output();
    }

    private static int N, K, L;
    private static int[][] BOARD;
    private static Map<Integer, String> COMMAND_MAP;

    private static void input() {
        N = inputProcessor.nextInt(); // 보드의 크기
        K = inputProcessor.nextInt(); // 사과의 개수
        BOARD = new int[N + 1][N + 1];
        for(int i = 1; i <= K; i++) {
            int x = inputProcessor.nextInt();
            int y = inputProcessor.nextInt();

            BOARD[x][y] = 1;
        }

        L = inputProcessor.nextInt();
        COMMAND_MAP = new HashMap<>();
        for(int i = 1; i <= L; i++) {
            int x = inputProcessor.nextInt();
            String c = inputProcessor.next();

            COMMAND_MAP.put(x, c);
        }
    }

    private static final int[][] DIR = {
            {0, 1},
            {1, 0},
            {0, -1},
            {-1, 0}
    };

    private static void pro() {
        Deque<Integer> snake = new ArrayDeque<>();
        snake.add(1);
        snake.add(1);

        BOARD[1][1] = 2; // 뱀 표시

        int i = 0; // 오른쪽 이동
        int time = 0;
        int dx = 1;
        int dy = 1;
        while(true) {
            dx += DIR[i][0];
            dy += DIR[i][1];

            if(dx < 1 || dy < 1 || dx > N || dy > N || BOARD[dx][dy] == 2) {
                time += 1;
                break;
            }

            if(BOARD[dx][dy] == 1) { // 사과가 있는 경우
                BOARD[dx][dy] = 2;
            } else { // 빈 공간
                int nx = snake.poll();
                int ny = snake.poll();
                BOARD[nx][ny] = 0; // 꼬리 제거
            }

            BOARD[dx][dy] = 2;
            snake.add(dx);
            snake.add(dy);

            time += 1;
            // 방향 전환*
            if(COMMAND_MAP.containsKey(time)) {
                String command = COMMAND_MAP.remove(time);
                i = nextDir(i, command);
            }
        }

        sb.append(time);
    }

    private static int nextDir(int i, String command) {
        if(command.equals("D")) { // 오른쪽 90도
            return (i + 1) % 4;
        }

        return (i - 1) < 0 ? 3 : (i - 1); // 왼쪽 90도
    }

    private static void output() {
        try (BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            bw.write(sb.toString());
            bw.flush();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    private static class InputProcessor {
        private BufferedReader br;
        private StringTokenizer st;

        public InputProcessor() {
            this.br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return st.nextToken();
        }

        public String nextLine() {
            String result = "";

            try {
                result = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }

            return result;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }
    
}