[백준] 3190번 : 뱀

뱀

---

풀이 방법

우리가 잘 알고있는 지렁이 게임(?)을 구현해보는 문제였다.
시뮬레이션 문제는 처음 풀어봤는데, 생각보다 쉽지 않았다.
하지만, 유형만 잘 이해해 놓는다면 다음엔 조금 더 쉽게 풀수 있을 것 같았다.!

문제에서 주어진 규칙을 차근차근 읽고 구체적으로 구현해야 했다.

이 문제에서 큐를 사용한 이유는 뱀의 이동 방식이 머리를 옮기고 꼬리는 자르는 방식으로 선입선출의 특성을 갖는 큐를 사용하면 쉽게 해결할 수 있었다.

그리고 키, 값을 갖는 Map을 사용해서 편하게 저장하고, 쉽게 값을 찾을 수 있었다.

배운 점

이런 시뮬레이션, 좌표 이동문제에서는 dx, dy 배열을 선언한 뒤, int mx = px + dx[index]; int my = py + dy[index]; 이처럼 움직일 좌표 mx, my를 구한 뒤, 이동할 수 있는지 없는지 판별하는 방식을 사용함을 알았다!

그리고 큐를 사용했는데, 큐의 제너릭으로 int 배열을 선언해서 사용해주었다. 큐의 메서드 중 하나인 contains()을 사용해서 큐 내에 있는 int 배열과 주어진 배열이 같은지 구별해 줄줄 알았는데, 어림 없었다..
그래서 for문을 통해서 mx, my 값 하나하나를 구분해서 판단했다..

이번 문제는 알아가는게 많은 문제였다!! 시간은 많이 걸렸지만, 다음에 비슷한 유형의 문제를 마주친다면 쉽게 해결할 수 있겠다는 자신감이 들었다!

---

코드

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

public class Main {
    static int n;
    static int[][] board;
    static Map<Integer,String> moveInfo = new HashMap<>();

    // 우(시작), 하(D-우측회전, index++), 좌(D-우측회전, index++), 상(D-우측회전, index++)
    static int index=0;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        board = new int[n+1][n+1];

        //사과의 위치
        for(int i=0;i<k;i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            board[a][b] = 1;
        }

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

        int result = solve();
        System.out.println(result);
    }
    static int solve(){
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{1,1});
        int time = 0;
        int px =1;
        int py =1;
        while(true){
            int mx = px + dx[index];
            int my = py + dy[index];
            time++;

            //벽에 부딪힘.
            if(mx < 1 || my < 1 || mx > n || my > n){
                return time;
            }
            
            //자기 몸에 부딪힘.
            for (int[] body : queue) {
                if(body[0]==mx && body[1]==my){
                    return time;
                }
            }

            //이동
            queue.add(new int[]{mx,my});

            //사과가 있다면
            if(board[my][mx] == 1){
                board[my][mx] = 0;
            } else{ //사과가 없다면
                queue.remove();
            }

            //방향 변경 확인
            if(moveInfo.containsKey(time)){
                String direction = moveInfo.get(time);
                if(direction.equals("L")){
                    index--;
                    if(index == -1){
                        index = 3;
                    }
                }
                else if(direction.equals("D")){
                    index++;
                    if(index == 4){
                        index = 0;
                    }
                }
            }

            px = mx;
            py = my;
        }
    }
}