[백준] 3190- 뱀 문제 풀이(자바,Java)

문제

3190번: 뱀

 

들어가며

뱀의 머리를 저장할 생각을 처음부터 왜 못했을까..

코드

package m03.d25;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Queue;

public class 뱀_3190 {
    static int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int k = Integer.parseInt(br.readLine());

        ArrayList<Apple> apples = new ArrayList<>();
        for (int i = 0; i < k; i++){
            int[] s = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt)
                    .toArray();
            apples.add(new Apple(s[0],s[1]));
        }

        Queue<Command> commands = new ArrayDeque<>();

        int l = Integer.parseInt(br.readLine());
        for (int i = 0; i < l; i++) {
            String[] s = br.readLine().split(" ");
            int time = Integer.parseInt(s[0]);
            String dir = s[1];
            commands.add(new Command(time, dir));
        }
        Queue<Snake> tails = new ArrayDeque<>();
        int time = 0;
        int currentDir = 0;
        Snake head = new Snake(0,0);
        while(true){
//			  이 부분 주석 푸시면 어떻게 좌표가 이동하는지 알 수 있어요
//            System.out.print("Snake positions at time " + time + ": head - (" + head.x +","+head.y+")|");
//
//            for (Snake snake : tails) {
//                System.out.print("(" + snake.x + "," + snake.y + ") ");
//            }
//            System.out.println();
            //시간에 따른 방향 변경
            if(!commands.isEmpty() && time >= commands.peek().time){
                Command poll = commands.poll();
                currentDir = (currentDir+ poll.dir + 4) % 4;
            }
            // 뱀 움직임 구현
            int newX = head.x + dir[currentDir][0];
            int newY = head.y + dir[currentDir][1];
            if (!canMove(tails,n,newX,newY)){
                break;
            }
            boolean findAppleFlag = false;
            for (var apple : apples){
                if(apple.isFind(newX, newY) && !apple.visited){
                    apple.visited = true;
                    findAppleFlag = true;
                    break;
                }
            }

            tails.add(head);
            if (!findAppleFlag){
                tails.poll();
            }

            head = new Snake(newX,newY);
            time++;
        }
        System.out.println(time+1);
    }

    private static boolean canMove(Queue<Snake> tails,int n, int x, int y){
        if (x >= n || y >= n || x < 0 || y < 0){
            return false;
        }
        for (Snake body : tails) {
            if (body.x == x && body.y == y) {
                return false;
            }
        }


        return true;
    }

    private static class Command{
        int time;
        int dir;

        public Command(int time, String dir) {
            this.time = time;
            if (dir.equals("L")){
                this.dir = -1;
            } else {
                this.dir = 1;
            }
        }
    }
    private static class Apple{
        int x;
        int y;
        boolean visited;

        public Apple(int x, int y) {
            this.x = x-1;
            this.y = y-1;
            this.visited = false;
        }

        public boolean isFind(int x, int y){
            return this.x == x && this.y == y;
        }
    }
    private static class Snake{
        int x;
        int y;

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

 

풀이

문제를 그대로 따라가면 된다

Queue<Snake> tails = new ArrayDeque<>();

 

다만, 뱀의 꼬리를 처리하는 것에 있어서 큐를 사용하면 편하다.

왜냐하면, 꼬리의 끝점이 언제나 큐의 맨 앞 부분에 위치할 수 있게 만들 수 있기 때문이다.

만약 도착할 위치에 사과가 없다면, 꼬리의 끝점인  queue의 peek을 poll하면 그만이다.

 

Snake head = new Snake(0,0);

큐를 사용할 경우에 머리까지 큐에 넣게 되면 이 값을 갱신하기가 정말 어려워진다.

이때문에 head라는 변수를 만들어 따로 저장한다.

 

방향 전환은 다음과 같이 처리한다.

static int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};

if(!commands.isEmpty() && time >= commands.peek().time){
    Command poll = commands.poll();
    currentDir = (currentDir+ poll.dir + 4) % 4;
}
// 뱀 움직임 구현
int newX = head.x + dir[currentDir][0];
int newY = head.y + dir[currentDir][1];

dir 이라는 2차원 배열을 만들고 이를 이용하여 방향을 전환한다.

여기서 기본 방향은 (0,1) 즉, -> 방향이므로 첫 번째 인덱스에 넣어두었다.

+1를 하게 되면, 오른쪽으로 회전하여 (1,0) 밑 방향으로 넘어가게 되는 형식이다.

-1를 하면 왼쪽으로 회전한다.

 

private static boolean canMove(Queue<Snake> tails,int n, int x, int y){
    if (x >= n || y >= n || x < 0 || y < 0){
        return false;
    }
    for (Snake body : tails) {
        if (body.x == x && body.y == y) {
            return false;
        }
    }


    return true;
}

이동하게될 새로운 좌표를 검사할 때, 이전 꼬리들과 충돌하는지를 파악해야한다.

 

이렇게 문제에 따라 코드를 작성하게 되면 문제를 풀 수 있다.