[BOJ/Gold4] 3190번 뱀 - JAVA[자바]

난이도 : 골드 4

유형 : 구현 / 시뮬레이션 / 큐

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

구현 시간 : 1시간

 

 

 

문제풀이

앞서 풀었던 시뮬레이션 / 구현 문제인 로봇 청소기보다 구현하는데 오랜 시간이 걸린 것 같다. 뱀의 길이는 조건에 따라 늘어나고, 늘어나는 뱀의 몸을 저장할 자료구조를 생각하는게 특히 고민할 부분이였던 것 같다.

[BOJ] 14503번 로봇 청소기 - JAVA[자바]

 

1. 보드(룸)의 크기와 사과 위치를 입력받아 모든 값을 0으로 채운다.
2. 뱀의 시작위치(0,0)와 방향(동)을 초기화한다.
3. 사과의 위치를 저장한다. 사과는 임의의 값인 1로 채웠다.
4. 뱀의 방향 변환 정보를 저장한다. Map 자료구조를 사용했고, time 을 key 값으로 방향 정보를 value 로 저장했다.
5. 게임 진행
   1. 매 초마다 뱀의 머리를 이동시키고 충돌 여부를 확인한다.
   2. 머리가 이동한 위치에 사과가 있으면 사과를 먹고 길이를 늘린다.
   3. 사과가 없다면 꼬리를 이동하여 길이를 유지한다.
      1. Deque 자료구조를 이용해서 뱀의 몸을 저장했다. 배열에는 몸통과 충돌여부를 확인해야 함으로 임의의 값인 2를 저장했다.
      2. 꼬리를 이동할 때는 deque.pollLast() 메서드를 통해 마지막 값을 삭제했다.
   4. 이후 입력된 방향 전환 시간을 확인하여 방향을 변경했다.

 

 

1차 시도 - 통과

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

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

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

        int time = 0;        // 시작 시간
        int d = 1;           // 동쪽

        // 뱀의 몸통을 저장하는 Deque 생성
        Deque<int[]> deque = new LinkedList<>();
        deque.addFirst(new int[]{0, 0});

        // 빈 곳 -> 0, 사과 -> 1, 뱀의 몸 -> 2
        int[][] room = new int[N][N];
        room[0][0] = 2;

        // 사과 위치 저장
        for (int i = 0; i < K; i++) {
            String[] appleLoc = br.readLine().split(" ");
            int appleX = Integer.parseInt(appleLoc[0]);
            int appleY = Integer.parseInt(appleLoc[1]);
            room[appleX-1][appleY-1] = 1;
        }

        // 뱀의 방향 변환 정보 저장
        int L = Integer.parseInt(br.readLine());

        Map<Integer, String> snakeDirection = new HashMap<>();
        for (int i = 0; i < L; i++) {
            String[] timeAndDir = br.readLine().split(" ");
            int turnTime = Integer.parseInt(timeAndDir[0]);
            snakeDirection.put(turnTime, timeAndDir[1]);
        }

        // 방향 정보 저장 변수
        Map<Integer, int[]> directionMap = new HashMap<>();
        directionMap.put(0, new int[]{-1, 0});     // 북
        directionMap.put(1, new int[]{0, 1});      // 동
        directionMap.put(2, new int[]{1, 0});      // 남
        directionMap.put(3, new int[]{0, -1});     // 서

        while (true) {
            time++;
            int[] directions = directionMap.get(d);
            int[] head = deque.peekFirst();
            int x = head[0] + directions[0];
            int y = head[1] + directions[1];

            // 충돌 확인
            if (x < 0 || x >= N || y < 0 || y >= N || room[x][y] == 2) {
                break;
            } else if (room[x][y] == 1) {
                deque.addFirst(new int[]{x, y});
                room[x][y] = 2;
            } else {
                deque.addFirst(new int[]{x, y});
                room[x][y] = 2;
                int[] tail = deque.pollLast();
                room[tail[0]][tail[1]] = 0;
            }

            // 뱀 방향 전환 정보 확인
            if (snakeDirection.containsKey(time)) {
                String direction = snakeDirection.get(time);
                if (direction.equals("D")) {
                    d = (d + 1) % 4; // 오른쪽
                } else if (direction.equals("L")) {
                    d = (d + 3) % 4; // 왼쪽
                }
            }
        }
        System.out.println(time);
    }
}