[BOJ] 뱀(3190)

[백준(BOJ)] 3190_뱀 JAVA

문제 : BOJ_3190번 뱀

문제 설명

매초 움직이면서 꼬리를 늘려가는 뱀 게임을 구현하는 문제입니다.

N*N 크기의 맵이 주어지고, 사과가 있는 각각의 위치와 뱀이 방향을 바꾸는 순간이 주어집니다.

이때 뱀이 움직인 방향에 사과가 있다면 사과를 먹고 꼬리가 늘어나지만, 사과가 없다면 기존의 꼬리 부분이 사라지고 뱀의 머리 부분이 늘어납니다.

또한 방향은 최초에 오른쪽으로 이동하며 이동방향을 기준으로 오른쪽이나 왼쪽으로 90도 회전할 수 있습니다.

---

Solution

구현

문제에서 주어진 대로 구현을 하면 됩니다.

뱀의 현재 머리 위치와 꼬리 위치를 계속 기록해 주면서, 이동한 곳에 사과가 있으면 머리 위치만 수정해 주고, 사과가 없을 시엔 꼬리 위치도 함께 수정해 줘야 합니다.

이때 꼬리 위치마다 어느 방향으로 이동했는지도 기록해 주어야 합니다.(lastMove)

또한 꼬리 위치가 바뀐다면 마지막 꼬리 위치에는 뱀이 존재하지 않는 것이므로 빈 공간으로 수정해 주어야 합니다.

이때 뱀이 존재한다고 체크한 부분으로 이동하거나, 지도 밖으로 벗어나는 순간을 정답으로 출력하면 됩니다.

---

Description

• dx[], dy[] 배열을 통해 이동방향을 정할 때, 배열의 값에서 +1일 시에는 오른쪽으로 회전, -1일 시에는 왼쪽으로 회전하게 좌표값을 지정해 주었습니다.
• 뱀의 방향 정보에서 시간인 X는 X 초에 방향을 회전시키는 게 아닌 X 초가 끝난 뒤에 방향을 전환하는 것입니다.(result==moveCnt+1)

---

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Pair{
    private int cnt;
    private String direction;

    Pair(int cnt, String direction){
        this.cnt = cnt;
        this.direction = direction;
    }

    public int getCnt() {
        return cnt;
    }

    public String getDirection() {
        return direction;
    }
}

public class Main {

    public static int[][] map;
    public static int[][] lastMove;
    public static int[] dx = {0,1,0,-1};
    public static int[] dy = {1,0,-1,0};
    public static int dir = 0;

    public static int changeDir(int dir, String command){
        if(command.equals("L")){
            if(dir==0) return 3;
            else return dir-1;
        }
        else {
            if(dir==3) return 0;
            else return dir+1;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        map = new int[n+1][n+1];
        lastMove = new int[n+1][n+1];
        st = new StringTokenizer(br.readLine());
        int k = Integer.parseInt(st.nextToken());
        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] = 2;
        }

        Queue<Pair> q = new LinkedList<>();

        st = new StringTokenizer(br.readLine());
        int l = Integer.parseInt(st.nextToken());
        for(int i=0;i<l;i++){
            st = new StringTokenizer(br.readLine());
            int cnt = Integer.parseInt(st.nextToken());
            String direction = st.nextToken();
            q.offer(new Pair(cnt,direction));
        }

        dir = 0;
        int result = 0;
        map[1][1] = 1;
        lastMove[1][1] = dir;
        int nowX = 1;
        int nowY = 1;
        int endX = 1;
        int endY = 1;
        int moveCnt = 0;
        String moveDir = "";
        if(!q.isEmpty()) {
            moveCnt = q.peek().getCnt();
            moveDir = q.peek().getDirection();
        }
        while(true){
            result++;
            if(result==moveCnt+1){
                q.poll();
                dir = changeDir(dir,moveDir);
                if(!q.isEmpty()) {
                    moveCnt = q.peek().getCnt();
                    moveDir = q.peek().getDirection();
                }
            }
            int nextX = nowX + dx[dir];
            int nextY = nowY + dy[dir];
            if(nextX<=0 || nextY<=0 || nextX > n || nextY > n) break;
            if(map[nextX][nextY]==1) break;
            lastMove[nowX][nowY] = dir;
            nowX = nextX;
            nowY = nextY;
            if(map[nextX][nextY]==2){
                map[nextX][nextY] = 1;
                continue;
            }
            else {
                map[nextX][nextY] = 1;
                map[endX][endY] = 0;
                int nowDir= lastMove[endX][endY];
                endX += dx[nowDir];
                endY += dy[nowDir];
            }
        }
        bw.write(String.valueOf(result));
        bw.flush();
        br.close();
        bw.close();
    }

}