[백준] 3190번 Java (Deque, 시뮬레이션)

동은·2024년 9월 25일

알고리즘

알고리즘 문제 풀이

목록 보기

6/18

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

💡문제

풀이

접근법 :

뱀이 차지하고 있는 좌표를 Deque에 저장한다.
뱀의 행동에 따라 머리 좌표를 추가해주고, 꼬리 좌표를 제거해주면 된다.

1. 방향 전환의 시간과 방향을 Map<시간, 방향>으로 받아 저장

      int l = Integer.parseInt(br.readLine());    // 방향 전환 횟수

      Map<Integer, Character> directionMap = new HashMap<>();

      for (int i = 0; i < l; i++) {	// 방향 입력 받아오기
        st = new StringTokenizer(br.readLine());
        int x = Integer.parseInt(st.nextToken());
        String c = st.nextToken();
        directionMap.put(x, c.charAt(0));  // 방향 정보 저장
      }

2. 뱀의 초기 위치와 설정

      Deque<int[]> snake = new ArrayDeque<>();
      snake.offer(new int[]{0,0});    // 뱀의 시작 위치
      int direction = 0;  // 최초 방향
      int time = 0;       // 시간
      int x = 0, y = 0;   // 뱀의 머리 위치

머리 위치 좌표는 (0, 0)에서 시작
방향 배열 dx, dy

      // 오른쪽, 아래, 왼쪽, 위
      static int[] dx = {0,1,0,-1};
      static int[] dy = {1,0,-1,0};

초기 방향은 0, 오른쪽 시작

3. 게임 시작

시간 1초 증가
머리 좌표 설정

      time++;
      x += dx[direction];
      y += dy[direction];

4. 게임이 종료되는 상황을 먼저 설정

벽과 만나는 경우

      x<0 || x>=n || y<0 || y>=n

자기 자신의 몸과 부딪히는 경우

static boolean isMine(Deque<int[]>snake, int x, int y){
        for(int[] body : snake){
            if(body[0] == x && body[1] == y){
                return true;
            }
        }
        return false;
    }

(x, y)가 뱀 몸통에 해당하는지 확인한다.
snake의 각 요소인 body로 순회하며 (x, y)가 뱀 몸통 좌표와 일치하는지 검사.

5. 사과 먹는 상황에 대해

사과가 있다면 : 사과를 먹고 꼬리는 그대로 둔다.

    board[x][y] = 0;	// 사과 좌표 -> 일반 좌표로
    snake.offerFirst(new int[]{x,y}); // 머리 좌표 추가

사과가 없다면 : 꼬리가 줄어든다.(꼬리 좌표 제거)

    snake.offerFirst(new int[]{x,y});	// 머리 좌표 추가
    snake.pollLast();	// 꼬리 좌표 제거

6. 방향 전환 시간

방향 map을 뒤져서 시간(key)이 된 경우 방향을 전환한다.
L : 왼쪽으로 90도 회전 (-1, 0)
D : 오른쪽으로 90도 회전 (1, 0)

		if(directionMap.containsKey(time)){
                char c = directionMap.get(time);
                if(c == 'L'){   // 왼쪽으로 90도 회전
                    direction = (direction + 3) % 4;
                } else if(c == 'D'){
                    direction = (direction + 1 ) % 4;
                }
            }

내 코드

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

public class Main {
    //방향 배열
    static int[] dx = {0,1,0,-1};
    static int[] dy = {1,0,-1,0};

    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());    // 사과의 개수
        StringTokenizer st;

        int [][] board = new int[n][n];     // 보드 배열
        
        // 사과가 있는 칸은 1로 표현
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            board[Integer.parseInt(st.nextToken())-1][Integer.parseInt(st.nextToken())-1] = 1;
        }

        int l = Integer.parseInt(br.readLine());    // 방향 전환 횟수
        Map<Integer, Character> directionMap = new HashMap<>();

        for (int i = 0; i < l; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            String c = st.nextToken();
            directionMap.put(x, c.charAt(0));  // 방향 정보 저장
        }

        // 뱀의 초기 위치 설정
        Deque<int[]> snake = new ArrayDeque<>();
        snake.offer(new int[]{0,0});    // 뱀의 시작 위치
        int direction = 0;  // 최초 방향
        int time = 0;       // 시간
        int x = 0, y = 0;   // 뱀의 머리 위치

        // 게임 진행
        while(true){
            time++;

            x += dx[direction];
            y += dy[direction];

            // 게임 종료 상황
            if(x<0 || x>=n || y<0 || y>=n || isMine(snake, x, y)){
                break;
            }
            // 사과가 있다면 : 사과 먹고 꼬리 그대로
            if(board[x][y] == 1){
                board[x][y] = 0;
                snake.offerFirst(new int[]{x,y});
            } else {    // 사과가 없다면 : 꼬리 하나 쪽 제거
                snake.offerFirst(new int[]{x,y});
                snake.pollLast();
            }

            // 방향 전환 시간
            if(directionMap.containsKey(time)){
                char c = directionMap.get(time);
                if(c == 'L'){   // 왼쪽으로 90도 회전
                    direction = (direction + 3) % 4;
                } else if(c == 'D'){
                    direction = (direction + 1 ) % 4;
                }
            }
        }
        System.out.println(time);
    }

    // 자신의 몸과 충돌하는지 확인하는 함수
    static boolean isMine(Deque<int[]>snake, int x, int y){
        for(int[] body : snake){
            if(body[0] == x && body[1] == y){
                return true;
            }
        }
        return false;
    }
}