[백준] 3190번_뱀_Java

문제 링크 👉🏻 https://www.acmicpc.net/problem/3190

👀 문제 접근

---

뱀 이동 게임이 종료되는 시간을 구하기

초기 뱀 사이즈는 $n * n$ 크기의 보드에서 한 칸을 차지한다.

사과를 먹으면 뱀의 길이가 한 칸 늘어나고, 뱀이 기어다니다가 벽이나 자기 자신의 몸과 부딪히면 게임이 종료된다.

🔎 해결 방식

---

입력과 저장

• 보드의 크기 n 과 n * n 크기의 2차원 배열인 map 을 선언 및 초기화 한다.
• 사과 개수 k 를 입력 받고, k 만큼 사과 위치를 입력 받는다. 이때 입력 받은 좌표에 맞게 map 에 사과 위치를 표시한다. ex) 3 4가 입력 됐을 때 map[3][4] = 2
  
• 뱀의 방향 변환 횟수 l 을 입력받고 방향 정보를 입력하여 저장한다.
  • 해당 정보를 저장할 적합한 자료구조가 떠오르지 않아 List<String[]> 으로 저장하도록 구현하였다.
  • 방향 전환할 시간은 중복되지 않기 때문에 LinkedHashMap<Integer, Char> 를 쓰면 될듯하다.
• 뱀의 방향 전환과 좌표 이동에 사용될 상수 mCol 과 mRow 를 선언한다.
  • 인덱스가 0일 때는 위, 1일 때 오른쪽, 2일 때 아래, 3일 때 왼쪽으로 좌표가 이동한다.

게임 시작

• 뱀의 몸 위치를 저장할 자료구조, 시간, 뱀 몸 방향을 저자할 변수를 선언한다.
  • 뱀의 머리와 꼬리의 좌표가 계속 변하기 위해 앞뒤로 push, pop이 가능한 deque 을 사용한다.
  • deque 에 뱀의 첫 시작 위치인 (1, 1)을 먼저 push한다.
  • 초기 방향은 오른쪽을 향하기 때문에 currDir 은 1로 초기화 하고, time 은 0으로 초기화 한다.
• 뱀의 방향 전환 정보를 저장한 direction 을 순회한다.

  • List<String[]> 으로 저장 했기 때문에, 몇 초 후에 방향을 전환할지에 대한 정보를 정수형으로 파싱하여 after 변수에 저장한다.

    뱀 전진

  • while 문으로 time 과 방향 전환 시간 after 가 같아질 때까지 반복한다.

  • 현재 뱀 머리 좌표 정보를 dq.peekFirst() 로 얻고, 1초 후에 위치할 좌표를 계산한다.
    - nRow = currHead[0] + mRow[currDir] , nCol = currHead[1] + mCol[currDir]
    - nRow 와 nCol 이 1보다 작거나 n 보다 큰 경우는 벽에 부딪힌 상황이기 때문에 time 을 리턴한다.
    - 또 map[nRow][nCol] 이 1일 때 뱀이 자기 자신과 부딪히는 상황이기 때문에 이 경우에도 time 을 리턴한다.
    - map[nRow][nCol] 이 2가 아닐 때, 그 위치에 사과가 없음을 뜻하므로, 꼬리 좌표인 덱의 마지막 요소를 제거한다. 그리고 map 에서 1로 저장된 꼬리 부분을 다시 0으로 수정한다.
    - 이동한 머리 좌표를 덱에 저장하고, map 에도 머리 좌표 부분을 1로 수정한다.

    방향 전환

  • time 과 after 가 같아지면 방향을 전환해야 한다.

  • 방향이 L일 때 왼쪽으로 전환해야 하므로 currDir 이 현재보다 1 작아져야 한다.

    • currDir = (currDir + 3) % 4 ⇒ 0에서 1 작아졌을 때 다시 3으로 돌아와야됨

  • 방향이 D일 때 오른쪽으로 전환해야 하므로 currDir 이 현재보다 1 커져야 한다.

    • currDir = (currDir + 1) % 4 ⇒ 3에서 1 커졌을 때 다시 0으로 돌아와야됨

  • 방향 전환 후에 while 문이 멈춰야한다.

  • 마지막 방향 전환 후에는 계속 전진해야 하기 때문에 break 없이 time 이 리턴될 때까지 while 문을 실행한다.

💻 구현 코드

---

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

public class Main {
    static int time;
    static int n;
    static int[][] map;
    static List<String[]> direction;

    static final int[] mCol = {0, 1, 0, -1};
    static final int[] mRow = {-1, 0, 1, 0};

    public static int runDummy() {
		    // 뱀 위치 좌표 저장
        Deque<int[]> dq = new ArrayDeque<>();
        dq.offerFirst(new int[]{1, 1});

				// 초기 방향은 오른쪽
        int currDir = 1;
        time = 0;

				// 방향 전환 저장 정보 순회
        for (String[] d : direction) {
        
		        // 몇 초 후에 방향 전환 할건지
            int after = Integer.parseInt(d[0]);
            
            while (true) {
		            // 현재 머리 좌표
                int[] currHead = dq.peekFirst();
                
                // 이동할 머리 좌표
                int nRow = currHead[0] + mRow[currDir];
                int nCol = currHead[1] + mCol[currDir];

                time += 1;
                
                // 벽에 부딪히는 경우 time 리턴
                if (nCol > n || nRow > n || nCol < 1 || nRow < 1) return time;

								// 자기 자신과 부딪히는 경우 time 리턴
                if (map[nRow][nCol] == 1) {
                    return time;
                }
								
								// 사과가 없을 때 꼬리 부분 pop
								// 꼬리가 이동했기 때문에 map에서도 0으로 변경
                if (map[nRow][nCol] != 2) {
                    int[] rm = dq.pollLast();
                    map[rm[0]][rm[1]] = 0;
                }

								// 새로운 머리 좌표 정보 앞에 push
                dq.offerFirst(new int[]{nRow, nCol});
                map[nRow][nCol] = 1;

								// 방향 전환할 시간과 현재 시간이 같아지면 방향 전환
                if (time == after) {
                    if (d[1].equals("L")) currDir = (currDir + 3) % 4;
                    else if (d[1].equals("D")) currDir = (currDir + 1) % 4;
                    
                    // 마지막 방향 전환 후에는 계속 전진해야 하기 때문에 break를 실행하지 않으
                    if (after != Integer.parseInt(direction.get(direction.size() - 1)[0])) break;
                }
            }
        }
        return time;
    }

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

        n = Integer.parseInt(br.readLine());
        int k = Integer.parseInt(br.readLine());

        map = new int[n + 1][n + 1];
        
        // 사과 위치 정보 저장
        for (int i = 0; i < k; i++) {
            String[] input = br.readLine().split(" ");
            map[Integer.parseInt(input[0])][Integer.parseInt(input[1])] = 2;
        }

				// 초기 뱀 위치
        map[1][1] = 1;

        int l = Integer.parseInt(br.readLine());
        direction = new ArrayList<>();

				// 뱀 방향 전환 정보 저장
				// List대신 LinkedHashMap 쓰면 될듯
        for (int i = 0; i < l; i++) {
            direction.add(br.readLine().split(" "));
        }

        System.out.println(runDummy());
    }
}

✨ 마무리

종종 하던 스네이크 게임이 생각나서 구현하면서 재미는 있었지만 그래도 난이도가 꽤 있는 편인것 같았다.

그래도 언제 멈출지, 방향 전환은 언제 할지만 잘 캐치 하면 충분히 풀 수 있는 문제였다.

마지막 방향 전환을 끝내고 나서는 그 방향으로 벽에 부딪히거나 몸에 부딪힐 때까지 계속 while문이 실행되도록 해야 하는데, 그 부분을 해결하는데 시간을 좀 잡아 먹은 것 같다.

그리고 글 쓰면서 알았던거! 방향 전환 정보를 List로 쓴 게 좀 아쉽다. 처음에 이 시간이 중복될 수 있을거란 생각을 왜 한건지 모르겠지만 이 생각 때문에 Map이 아닌 List로 쓰게 됐다… 다시 구현한다면 LinkedHashMap을 써서 인티져로 파싱할 일 없이 편하게 구현 할래..😖
대략 3주동안 이것저것 할게 많아서(핑계 ㅎ 그래도 진짜 좀 바빴음..) 손 놓고 있었는데 다시 빡세게 공부해야겠당💪🏻