[백준 3190] 뱀

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

---

문제

---

아이디어

1. 보드 초기화, 사과 위치 설정
2. 방향 변환 정보 저장
3. 방향 벡터 설정
4. 회전 (시계 / 반시계)
5. 뱀이 지나가는 경로 확인
6. 게임 종료 조건을 만족하는지 체크(보드 범위 벗어남 / 자기 몸에 부딪힘)

1. 보드 초기화, 사과 위치 설정

: 보드의 크기 N과 사과의 갯수 K개를 2차원 int[][] 배열에 저장한다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 1. 보드 초기화, 사과 위치 설정
int N = Integer.parseInt(br.readLine());
int[][] board = new int[N][N];
int K = Integer.parseInt(br.readLine());
for(int apple = 0; apple < K; apple++){
    String[] input = br.readLine().split(" ");
    int row = Integer.parseInt(input[0]);
    int col = Integer.parseInt(input[1]);
    board[row-1][col-1] = -1;
}

 

2. 방향 변환 정보 저장

: 주어진 방향 변환 정보를 저장하기 위해 Vector 클래스를 생성. 멤버 변수로 time과 direction을 지정하여 추후 해당 시간이 됐을 때, 그에 맞는 방향을 적용시키기 위함. 

이후 Queue에 방향 변환 정보들을 저장함. (해당 time이 지난 방향 변환 정보는 필요없기 때문에 poll 하기 위함)

static class Vector {
    int time;
    char direction;

    public Vector(int time, char direction) {
        this.time = time;
        this.direction = direction;
    }
}

// 2. 방향 변환 정보 저장. (클래스)
Queue<Vector> directions = new LinkedList<>();
int L = Integer.parseInt(br.readLine());
for(int dir = 0; dir < L; dir++){
    String[] input = br.readLine().split(" ");
    Vector vector = new Vector(Integer.parseInt(input[0]), input[1].charAt(0));
    directions.add(vector);
}

 

3. 방향 벡터 설정

: 초기 뱀의 진행 방향은 우측 이기 때문에 (우 -> 하 -> 좌 -> 상) 시계방향을 기준으로 방향 벡터 배열을 설정하였음.

// 3. 방향 벡터 설정 (우, 하, 좌, 상)
int[] dx = {1, 0, -1, 0};
int[] dy = {0, 1, 0, -1};

 

4. 회전 (시계 / 반시계)

: 입력 받은 방향 변환 정보의 문자("D", "L")에 따라 각각 시계 / 반시계 방향으로 회전. 초기 설정을 (우 -> 하 -> 좌 -> 상) 으로 했기에, 시계 방향은 인덱스를 +1 해주고, 반시계 방향은 -1 씩 해주면 됨.

// 해당 시간 됐을 때 방향 전환
if(time == checkV.time) {
    if(checkV.direction == 'D') {
        dxIndex = (dxIndex+1)%4;
        dyIndex = (dyIndex+1)%4;
    }
    else if(checkV.direction == 'L') {
        if(dxIndex == 0)
            dxIndex = 3;
        else
            dxIndex--;

        if(dyIndex == 0)
            dyIndex = 3;
        else
            dyIndex--;
    }
}

 

5. 게임 시작

: time을 1씩 늘려가며 뱀을 진행 방향으로 1칸씩 이동. 현재 뱀이 위치한 칸은 1, 빈칸은 0, 사과가 있는 칸은 -1 으로 표현.

• 이동하려는 칸을 Queue에 저장
• 이동하려는 칸에 사과가 있다면 뱀의 몸길이 +1
• 뱀의 몸길이보다 Queue의 크기가 크다면 poll. (뱀이 지나온 칸을 다시 0으로

뱀이 이동하려는 칸이 보드의 범위를 벗어나거나, 자기 몸이 있는 칸(1이 저장된 칸) 일때 break

while(true) {
    time++;
    int nx = x + dx[dxIndex];
    int ny = y + dy[dyIndex];
    
    // 종료 조건
    if(nx >= N || ny >= N || nx < 0 || ny < 0 || board[ny][nx] == 1) {
        break;
    }

    if(board[ny][nx] == -1){
        length++;
    }

    board[ny][nx] = 1;
    x = nx;
    y = ny;
    queue.add(new Pos(nx, ny));

    if(queue.size() > length) {
        Pos pos = queue.poll();
        board[pos.y][pos.x] = 0;
    }
}

---

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Impl_05 {
    static class Pos {
        int x;
        int y;
        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static class Vector {
        int time;
        char direction;

        public Vector(int time, char direction) {
            this.time = time;
            this.direction = direction;
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 1. 보드 초기화, 사과 위치 설정
        int N = Integer.parseInt(br.readLine());
        int[][] board = new int[N][N];
        int K = Integer.parseInt(br.readLine());
        for(int apple = 0; apple < K; apple++){
            String[] input = br.readLine().split(" ");
            int row = Integer.parseInt(input[0]);
            int col = Integer.parseInt(input[1]);
            board[row-1][col-1] = -1;
        }

        // 2. 방향 변환 정보 저장. (클래스)
        Queue<Vector> directions = new LinkedList<>();
        int L = Integer.parseInt(br.readLine());
        for(int dir = 0; dir < L; dir++){
            String[] input = br.readLine().split(" ");
            Vector vector = new Vector(Integer.parseInt(input[0]), input[1].charAt(0));
            directions.add(vector);
        }

        // 3. 방향 벡터 설정 (상,하,좌,우)
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};

        // 게임시작 - 초기 위치 : (0, 0) / 초기 방향 상태 : 오른쪽 (x + 1, y + 0)
        int x = 0, y = 0;
        board[x][y] = 1;
        int length = 1;
        int time = 0;
        int dxIndex = 0;
        int dyIndex = 0;
        Queue<Pos> queue = new LinkedList<>();
        queue.add(new Pos(x, y));
        Vector checkV = directions.poll();

        while(true) {
            time++;
            int nx = x + dx[dxIndex];
            int ny = y + dy[dyIndex];

            if(nx >= N || ny >= N || nx < 0 || ny < 0 || board[ny][nx] == 1) {
                break;
            }

            if(board[ny][nx] == -1){
                length++;
            }

            board[ny][nx] = 1;
            x = nx;
            y = ny;
            queue.add(new Pos(nx, ny));

            if(queue.size() > length) {
                Pos pos = queue.poll();
                board[pos.y][pos.x] = 0;
            }
            // 해당 시간 됐을 때 방향 전환
            if(time == checkV.time) {
                if(checkV.direction == 'D') {
                    dxIndex = (dxIndex+1)%4;
                    dyIndex = (dyIndex+1)%4;
                }
                else if(checkV.direction == 'L') {
                    if(dxIndex == 0)
                        dxIndex = 3;
                    else
                        dxIndex--;

                    if(dyIndex == 0)
                        dyIndex = 3;
                    else
                        dyIndex--;
                }

                if(!directions.isEmpty())
                    checkV = directions.poll();
            }
        }

        System.out.println(time);
    }
}