[백준](Java) 3190 - 뱀

문제 링크

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

문제 풀이

시뮬레이션은 항상 문제를 이해하는데 제일 시간이 오래걸리는것 같다. 긴 문제를 보면서 정리하는 습관을 항상 키워야 할것 같다.
뱀이 움직일 지도를 map으로 만들었고 사과의 위치를 1로 설정했다.
뱀의 몸통이 있는 위치를 나타내기 위해서 chk를 생성
방향이 바뀌는 시점을 저장하기 위해서 Map에다가 저장했다. key값을 바뀌는 시간, value값으로 방향을 설정으로 해서 map.get(시간)을 통해서 특정 시간에 방향을 바꿀수 있도록 했다.

        for (int i = 0; i < m; i++) {
            map[sc.nextInt() - 1][sc.nextInt() - 1] = 1;
        }
        int k = sc.nextInt();
        for (int i = 0; i < k; i++) {
            dirmap.put(sc.nextInt(), sc.next());
        }

1행 1열을 (0,0)이라는 가정하에 시작했다.
초기 시작(answer)은 0초, 우측방향으로부터 움직이기 시작하므로 diry,dirx는 상우하좌 순으로 시계방향대로 설정되어있다. 그래서 우측방향의 index=1이므로 dir=1로 설정
그리고 몸통길이는 초기에는 1이다.
(솔직히 지나고보니깐 head는 굳이 필요없는 값이었다. -> 대신 가독성이 좋아졌던것 같기도 하고...)
또한 뱀이 움직였던 좌표를 history에다가 넣고 저장하여 몸통의 길이만큼 history에서 값을 꺼내서 사요하면 된다고 생각했다.

나머지는 주석을 단 순서대로
시간 증가 -> 머리의 좌표 이동 -> 머리의 좌표 체크 -> 몸통의 위치를 chk[][]=true로 표시 이를 위해 매초마다 chk를 초기화하고, history의 맨 마지막(최근값)부터 몸통의 길이만큼 꺼내씀-> 그리고 머리가 몸통에 닿는지 체크, 닿지 않는다면 history에 이동 좌표 추가 -> 사과를 먹을수 있다면 몸통의 길이 늘림 -> 방향전환이 된다면 방향 전환 왼쪽으로 가면 반시계이므로 dir을 -, 오른쪽으로 방향전환이 된다면 시계방향이므로 dir을 + 해주었다.

코드

import java.util.*;

public class Main {

    static int n;
    static int[][] map;
    static boolean[][] chk;

    static int[] diry = {-1, 0, 1, 0};
    static int[] dirx = {0, 1, 0, -1};
    static Map<Integer, String> dirmap = new HashMap();
    static List<Node> history = new ArrayList();

    static class Node {
        int y;
        int x;

        public Node(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        map = new int[n][n];
        chk = new boolean[n][n];
        int m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            map[sc.nextInt() - 1][sc.nextInt() - 1] = 1;
        }
        int k = sc.nextInt();
        for (int i = 0; i < k; i++) {
            dirmap.put(sc.nextInt(), sc.next());
        }
        System.out.println(gamestart(0, 0));
    }

    public static int gamestart(int y, int x) {
        int answer = 0;
        int dir = 1; //우측으로 시작
        int bodylen = 1;
        Node head = new Node(y, x);
        history.add(new Node(y, x));
        while (true) {
            answer++;
            head.y = diry[dir] + head.y;
            head.x = dirx[dir] + head.x;
            
            //머리가 범위를 벗어난 경우에 종료  
            if (!(head.y > -1 && head.y < n && head.x > -1 && head.x < n)) {
                break;
            }
            
            //현재 몸통의 위치 최신화  
            for (int i = 0; i < n; i++) {
                Arrays.fill(chk[i], false);
            }
            for (int i = 0; i < bodylen; i++) {
                chk[history.get(history.size() - 1 - i).y][history.get(history.size() - 1 - i).x] = true;
            }
            
            //머리가 몸통에 닿으면 종료, 아닌경우에는 이동경로에 현재위치를 남긴다.
            if (chk[head.y][head.x]) {
                break;
            } else {
                history.add(new Node(head.y, head.x));
            }
            
            //사과 먹기
            if (map[head.y][head.x] == 1) {
                map[head.y][head.x] = 0;
                bodylen++;
            }
            
            //방향전환
            if (dirmap.containsKey(answer)) {
                if (dirmap.get(answer).equals("L")) { //왼쪽 -> 반시계 방향
                    dir = dir - 1 == -1 ? 3 : dir - 1;
                } else {
                    dir = dir + 1 == 4 ? 0 : dir + 1;
                }
            }
        }
        return answer;
    }
}