[백준] 3190번 / Java / 뱀

문제 - (https://www.acmicpc.net/problem/3190)

어렸을 때 오래된 게임기로 해봤던 게임이다. Dummy라는 도스 게임인데 전형적인 꼬리잡기 게임을 구현하는 문제였다.

이동하면서 '사과'를 먹으면 몸의 길이가 늘어나고 계속해서 이동하다가 벽이나 자신의 몸에 부딪히면 게임이 끝난다.

 

1. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
2. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
3. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
4. 뱀의 머리가 몸이나 벽에 닿으면 게임은 끝난다

 

 

📌 개선

• 뱀은 먼저 몸의 길이를 늘린 다음에 갈 곳에 사과가 있는지, 벽이 있는지, 자신의 몸이 있는지 확인한다는 것을 염두
  == 항상 문제 확인을 섬세하게 해라
• 처음 문제 풀이를 시작할 때, 자료구조 선택이 정말 중요하다는 것을 느꼈다. Deque를 사용했으면 풀이시간을 단축할 수 있었을 거라 생각한다
• 뱀이 회전하는 것은 0 1 2 3 으로 둬서 차례로 오른쪽, 아래, 왼쪽, 위로 회전하도록 설정해도 됨. 왜냐면 오른쪽으로 회전하면 0123 순서고 왼쪽으로 회전하면 3210 순서니까 그리고 이것은 %4 를 해줌으로써 간단히 구현할 수 있다
  나는 회전 코드를 노가다로 구현했는데 %하나로 처리가 가능했다 ㅠㅠ

if (!turn.isEmpty() && time == Integer.parseInt(turn.get(0)[0])) {
	if (turn.get(0)[1].equals("L")) dir--; // 왼쪽 회전
	else dir++; // 오른쪽 회전

	if (dir < 0) dir = 3;
	else if (dir > 3) dir = 0;

    turn.remove(0);
}

// 위처럼 할 필요가 없다!
dir = (dir + 1) % 4; // 오른쪽 회전
dir = (dir + 3) % 4; // 왼쪽 회전

 

• dy, dx를 좀 더효율적으로 사용할 수 있도록 연습해야 겠다.
  나는 moveFromDir이라는 함수를 만들어서 뱀이 가려는 방향에 따라 switch문 별로 이동할 곳을 찾았는데,
  다른 블로그를 찾아보니 더 효율적인 방법이 있었다.
  회전 방향을 0,1,2,3으로 정했으니 그 방향별로 dx, dy 배열을 만들어버리면 된다.

int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};

int nx = snake.getHead()[0] + dx[snakeDir];
int ny = snake.getHead()[1] + dy[snakeDir];

// snakeDir이 1이면 -1,0 (위로 이동)
// snakeDir이 2이면 0,1 (우로 이동) ... 이런식

 

 

 

😅실수

• 저번과 똑같은 실수를 저질렀다... 배열의 값이 아니라 주소를 참조해버려서 값을 연쇄적으로 변경시켜 버린것... 이 실수는 항상  머릿속에 넣어두고 코딩해야겠다.. 왠만하면 주소참조 자체를 안하는 방향으로 코드를 짜야겠다. (아마 필요한 경우엔 인지할 수 있을 것이다. 나는 자꾸 인지도 못한채 주소참조해버려서 문제가 된 것)
• 문제에서 짜라는 대로 짜면 되는데 거길 대강 확인하고 넘어가서 실수하는 바람에 디버깅하느라 시간을 다 날렸다
  "먼저 뱀은 몸길이를 늘린 다음에 머리를 다음 칸에 위치시킨다"는 조건을 놓쳐서 오답원인을 찾는 것에 시간을 많이 썼다

 

 

 

코드를 보려면 '더보기' 클릭

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

/**
 * 2시간 14분 .. 시뮬레이션 문제 너무 오래걸린다
 */
public class _3190_Snake {
    static int[][] map;
    static int N;
    static ArrayList<String[]> turn;
    static int[] right = {0, 1}, left = {0, -1}, up = {-1, 0}, down = {1, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N + 2][N + 2];
        // 맵 바깥은 -1
        for (int i = 0; i < N + 2; i++)
            for (int j = 0; j < N + 2; j++)
                if (i == 0 || j == 0 || i == N + 1 || j == N + 1) map[i][j] = -1;

        int K = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            map[x][y] = 1;
        }

        int L = Integer.parseInt(br.readLine());
        String[] _turn = new String[2];
        turn = new ArrayList<>();
        for (int i = 0; i < L; i++) {
            st = new StringTokenizer(br.readLine());
            turn.add(new String[]{st.nextToken(), st.nextToken()});
        }

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

    static int dummy() {
        Snake snake = new Snake(new int[]{1, 1});

        int time = 0;
        int dir = 0; // 0:right, 1:
        while (true) {
            // 시간 경과
            time++;

            // 뱀을 이동시킨다
            int[] movedPos = moveFromDir(dir, snake.getHead()); // 이동할 위치
//            System.out.println(movedPos[0] + "," + movedPos[1]);
            if (map[movedPos[0]][movedPos[1]] == 1) { // 사과가 있음
                snake.move(movedPos, true);
                map[movedPos[0]][movedPos[1]] = 0; // 사과를 먹음
            } else if (map[movedPos[0]][movedPos[1]] == -1) { // 벽임
                break;
            } else { // 빈 칸임 그냥 이동
                snake.move(movedPos, false);
            }

            // 뱀이 이동했는데 몸을 만남
            if (snake.isMeetBody()) {
                break;
            }

            // 뱀의 머리를 미리 회전시켜 놓는다
            if (!turn.isEmpty() && time == Integer.parseInt(turn.get(0)[0])) {
                if (turn.get(0)[1].equals("L")) dir--; // 왼쪽 회전
                else dir++; // 오른쪽 회전

                if (dir < 0) dir = 3;
                else if (dir > 3) dir = 0;

                turn.remove(0);
            }
        }
        
        return time;
    }

    static int[] moveFromDir(int dir, int[] pos) { // 뱀의 이동방향 확인
        int[] movingDir;
        int[] ret = new int[2]; /* pos가 snake body 요소 배열의 주소를 참조하기 때문에 함부로 변경해선 안됨 */

        switch (dir) {
            case 0:
                movingDir = right;
                break;
            case 2:
                movingDir = left;
                break;
            case 3:
                movingDir = up;
                break;
            case 1:
                movingDir = down;
                break;
            default:
                throw new IllegalStateException("Unexpected value: " + dir);
        }
        for (int i = 0; i < 2; i++) {
            ret[i] = pos[i] + movingDir[i];
        }

        return ret;
    }

    static class Snake {
        ArrayList<int[]> body;
        int[] preCutTail;

        Snake(int[] start) {
            body = new ArrayList<>();
            body.add(start);
        }

        void move(int[] pos, boolean eatApple) {
            if (eatApple) {
                body.add(0, pos);
            } else {
                body.add(0, pos);
                preCutTail = body.remove(body.size() - 1);
            }
        }

        int[] getHead() {
            return body.get(0);
        }

        int[] getTail() {
            return body.get(body.size() - 1);
        }

        boolean isMeetBody() {
            if (body.size() < 4) return false;
            int[] head = {getHead()[0], getHead()[1]};
            for (int i = 1; i < body.size(); i++) {
                if (head[0] == body.get(i)[0] && head[1] == body.get(i)[1]) {
                    return true;
                }
            }
            if (preCutTail != null && preCutTail[0] == head[0] && preCutTail[1] == head[1]) return true;
            return false;
        }
    }
}