[백준 JAVA] 3190번: 뱀

뱀

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

import java.io.*;
import java.util.*;

public class Main {
    public static int N, K, L, time = 1, dir = 1, size = 1;
    public static List<int[]> snake = new LinkedList<>();
    public static int[][] map;
    public static int[] dr = {-1, 0, 1, 0};
    public static int[] dc = {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());
        K = Integer.parseInt(br.readLine());
        map = new int[N][N];
        map[0][0] = 1;
        snake.add(new int[] {0, 0});
        for(int i = 0; i < K; i++){
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            map[r - 1][c - 1] = 2;
        }
        L = Integer.parseInt(br.readLine());
        for(int i = 0; i < L; i++){
            st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken());
            char d = st.nextToken().charAt(0);
            while(time <= t){
                int[] head = snake.get(size - 1);
                int nr = head[0] + dr[dir];
                int nc = head[1] + dc[dir];
//                System.out.println(time + " " + (nr + 1) + " " + (nc + 1) + " " + size);

                // 벽에 닿거나 몸과 부딫히면 종료
                if(nr < 0 || nr >= N || nc < 0 || nc >= N || map[nr][nc] == 1) {
                    System.out.println(time);
                    System.exit(0);
                }



                // 2. 사과가 있다면 사이즈만 추가
                if(map[nr][nc] == 2) {
                    size += 1;
                } // 3. 사과가 없다면 꼬리 삭제
                else {
                    int[] tail = snake.get(0);
                    snake.remove(0);
                    map[tail[0]][tail[1]] = 0;
                }

                // 1. 머리를 다음칸에 위치시킨다.
                map[nr][nc] = 1;
                snake.add(new int[] {nr, nc});

                time++;
            }
            if(d == 'L') dir = (dir - 1 + 4) % 4;
            else dir = (dir + 1) % 4;
        }

        while(true){
            int[] head = snake.get(size - 1);
            int nr = head[0] + dr[dir];
            int nc = head[1] + dc[dir];
//            System.out.println(time + " " + (nr + 1) + " " + (nc + 1) + " " + size);

            // 벽에 닿거나 몸과 부딫히면 종료
            if(nr < 0 || nr >= N || nc < 0 || nc >= N || map[nr][nc] == 1) {
                System.out.println(time);
                System.exit(0);
            }

            // 2. 사과가 있다면 사이즈만 추가
            if(map[nr][nc] == 2) {
                size += 1;
            } // 3. 사과가 없다면 꼬리 삭제
            else {
                int[] tail = snake.get(0);
                snake.remove(0);
                map[tail[0]][tail[1]] = 0;
            }

            // 1. 머리를 다음칸에 위치시킨다.
            map[nr][nc] = 1;
            snake.add(new int[] {nr, nc});

            time++;
        }
    }
}

 

시간이 굉장히 오래걸렸다. 오랜만에 구현문제를 풀어서 그런가 몇번이고 헤맸다.

문제에서는 사과가 주어지는 행 열 순서를 착각했고 시간초의 흐름 착각, System.exit(1)로 하면 idle에서는 잘돌아가지만 서버에서는 NZEC 런타임 에러가 발생한다. 종료할때는 반드시 System.exit(0)으로 0을 반환해줘야한다.

 

System.exit(0) 는 정상종료, System.exit(1)은 비정상 종료를 뜻한다.

 

처음에는 뱀의 머리와 꼬리만 배열에 저장해두고 이값으로 이동을 표현하려 했지만 머리의 움직임은 문제가 없지만 꼬리는 언제 꺾여야 하는지 알 수가 없었다. 따라서 뱀과 같이 이어진 LinkedList 형태로 모든 몸통과 꼬리 머리를 하나의 리스트로 저장하여 관리했다.

 

풀이 과정

1. 머리가 움직이는 경우는 항상 있으므로 머리를 우선 움직인 후, 벽에 닿거나 몸에 닿지 않았는지 판단하고 닿았다면 시간을 출력후 반환

 

2. 머리를 맵에 표시하고 리스트에 넣어준다. 하지만 맵에 머리를 먼저 표시하면 사과가 있었는지 없었는지 알 수 없어서 이 부분을 가장 마지막으로 바꿔주었다.

 

3. 사과의 유무에 따라 꼬리를 삭제할지 그대로 냅둘지 결정한다. 이 부분은 문제에서 친절하게 설명되어있기 때문에 좀 더 편하게 구현할 수 있었다.

 

4. 방향을 바꾸는 시간이 되었다면 방향을 바꿔준다.

 

회고

1. 시스템 정상종료는 System.exit(1) 이다. 뭔가 이렇게 코딩하면 아쉽다. 그냥 함수를 하나 만들어서 리턴해주는게 더 깔끔한 풀이가 되는것 같다.

 

2. 아직 시간초의 흐름이나 맵에서 표시하는 것들의 순서를 더 꼼꼼히 읽고 문제 푸는 습관을 들이자.

 

3. 구현을 바로 하는것보다 이제는 설계를 먼저 탄탄하게 하고 문제를 풀어야될꺼같다. 설계를 먼저 해봤다면 머리나 꼬리를 이차원 배열로 두는 행동은 하지 않았을것 같다.

 

4. 이번 문제는 변수가 헷갈려서 틀리진 않았지만 풀이를 보니 나중에 이렇게 풀었다간 헷갈릴꺼같다. 변수명이나 풀이과정을 좀더 명확하게 정의하고 문제를 풀자.

 

GPT 회고

1. LinkedList에서 snake.get(size - 1)은 시간복잡도가 O(N)이므로 이것을 리스트로 관리하지 말고 Deque로 관리하라

2. size의 변수 불필요 : list나 deque의 size로도 충분하므로 굳이 만들어서 쓰면 오히려 버그나 가독성이 안좋아 질 수 있음

3. 중복요소 로직 제거: 뱀을 움직이는것이 for문 안과 밬에 두번 중복되므로 

4. 조기종료 지양 : System.exit(0)는 문제에는 지장 없지만 함수형으로 만들어서 return으로 끝내라

5. 자료구조 쪼개기(권장) : 사과와 몸통을 섞으면 분기가 복잡해지므로 이거를 나눠서 관리하면 실수할 확률이 조금 더 줄어든다.

6. 매 이동마다 int 배열을 생성하면 객체가 계속 생기므로 deque를 이용하면 GC 부담이 줄어듬

 

또한 문제는 맞았지만 생각하지 못했던것은 바로 이전에 꼬리가 위치했던 곳으로 이동하는것은 사과가 없을때 충돌이 아니므로 이것을 처리해줘야한다. 반례가 테스트코드에는 없었지만 충분히 다른 문제에는 있을만한 경우이다.

 

즉 꼬리를 먼저 제거하고 머리를 이동해야한다.

 

다시 코드를 짜보았다.

 

import java.io.*;
import java.util.*;

public class Main {
    public static int N, K, L, time = 0, dir = 1;
    public static Deque<int[]> snake = new ArrayDeque<>();
    public static int[][] apple, map;
    public static HashMap<Integer, Character> turn = new HashMap<>();
    public static int[] dr = {-1, 0, 1, 0};
    public static int[] dc = {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());
        K = Integer.parseInt(br.readLine());
        apple = new int[N][N];
        map = new int[N][N];

        for(int i = 0; i < K; i++){
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken()) - 1;
            apple[r][c] = 1;
        }

        // 초기 위치 (0, 0)
        map[0][0] = 1;
        snake.add(new int[] {0, 0});

        // 회전 명령 저장
        L = Integer.parseInt(br.readLine());
        for(int i = 0; i < L; i++){
            st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken());
            char d = st.nextToken().charAt(0);
            turn.put(t, d);
        }

        // 시뮬레이션
        while(true){
            time++;
            if(!move()){
                System.out.println(time);
                return;
            }
            // t초가 지난 직후 회전
            if(turn.containsKey(time)){
                char d = turn.get(time);
                if(d == 'L') dir = (dir + 3) % 4;
                else dir = (dir + 1) % 4;
            }
        }
    }

    public static boolean move(){
        int[] head = snake.peekLast();
        int nr = head[0] + dr[dir];
        int nc = head[1] + dc[dir];

        // 몸, 벽충돌
        if(nr < 0 || nr >= N || nc < 0 || nc >= N || map[nr][nc] == 1) {
            return false;
        }

        // 사과가 있다면
        if(apple[nr][nc] == 1) {
            apple[nr][nc] = 0;
        } else {
            // 사과가 없다면
            int[] tail = snake.pollFirst();
            map[tail[0]][tail[1]] = 0; // 꼬리 삭제
        }

        // 머리를 다음칸에 위치시킨다.
        snake.addLast(new int[]{nr, nc});
        map[nr][nc] = 1;

        return true;
    }
}

 

다시 풀어봤는데 이 문제에서는 꼬리가 먼저 없어지면 안된다. 꼬리가 없어지기 전에 머리가 몸 즉, 꼬리에 부딪혀도 종료이다.

 

문제에 나와있는 순서로 푸는것이 우선이다. 아마 이 문제를 낸 사람은 이 게임을 제대로 해보지 않은것같다.