[BOJ 3190] 뱀

뱀

BOJ 3190 : 뱀

해설

처음에 이 문제를 풀 때, 제 시간에 풀지 못했다. 꼬리, 몸통, 머리 부분이 이해가 잘 안갔었는데 이 부분에 대한 해설은 다음과 같다.

# 꼬리, 몸통, 머리
예를들어 뱀이 (0, 0)에서 시작해서 계속 사과를 먹으며 우측으로 이동해 (0, 3)까지 간 상태라면
queue = (앞=꼬리) { (0,0), (0,1), (0,2), (0,3) } (뒤=머리) 가 된다.
사과를 못 먹어서 꼬리부분을 당겨야 되는 상황이라면 꼬리 위치의 값을 빈 값으로 설정하면 된다.

이 문제의 핵심은 Queue 를 사용한다는 것을 빨리 눈치 채야하는 것 같다. 그리고 나머지는 구현 문제 답게, 문제에 나와있는 조건들에 따라 차근차근 구현하면 되는 것 같다.

• Strategy
  • 전략(Strategy) 이라는 클래스를 만들어 방향 정보와 초를 필드로 가지게 했다.
• Position
  • Position 은 뱀위 위치(꼬리, 몸통, 머리)를 나타내는 좌표를 담을 수 있도록 하였다.

알고리즘 문제들 중 방향(Ex. 회전 후 이동)과 같은 문제 유형은 다음과 같은 코드가 거의 들어가는 것 같다.

// 방향 전환 D(right) 기준으로 동(초기방향) -> 남 -> 서 -> 북
// 방향 전환 L(left) 기준으로 동(초기방향) -> 북 -> 서 -> 남
private static int dx[] = {0, 1, 0, -1};
private static int dy[] = {1, 0, -1, 0};

초기 위치가 (1,1) 이며, 동쪽을 바라보고 있을 때, 오른쪽 방향(or 시계 방향) 으로 90 도로 회전하면 남쪽을 바라보게 된다. 그리고 남쪽으로 이동하면 (1,1) -> (2,1) 이 된다. 남쪽에서 다시 시계 방향으로 회전하면 서쪽을 바라보게 되고, 서쪽으로 이동하면 (2,1) -> (2,0) 이 된다.

이런식으로 방향에 따라 변화는 좌표를 계산하기 위한 함수를 제공할 수 있는데 다음과 같다.

// 회전
public static int turn(int direction, char c) {
    if (c == 'L') {
        direction = (direction == 0) ? 3 : direction - 1;
    } else {
        direction = (direction + 1) % 4;
    }
        return direction;
}

문제에서 주어지는 방향 조건에 맞게 함수 내부 구현을 다르게 해주면 된다.

구현

class Strategy {

    private int seconds;
    private char direction; 

    public Strategy(int seconds, char direction) {
        this.seconds = seconds;
        this.direction = direction;
    }

    public int getSeconds() {
        return seconds;
    }

    public char getDirection() {
        return direction;
    }
}

class Position {

    private int x;
    private int y;

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

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }
}

public class Main {

    private static int N; // 보드의 크기
    private static int K; // 사과의 위치
    private static int L; // 방향 변환 횟수

    private static int[][] square;
    private static final int EMPTY = 0; // 빈 값
    private static final int APPLE = Integer.MAX_VALUE; // 사과과 존재하는 위치
    private static final int SNAKE = Integer.MIN_VALUE; // 뱀이 존재하는 위치
    private static List<Strategy> strategies = new ArrayList<>(); // 이동 전략

    // 방향 전환 D(right) 기준으로 동(초기방향) -> 남 -> 서 -> 북
    // 방향 전환 L(left) 기준으로 동(초기방향) -> 북 -> 서 -> 남
    private static int dx[] = {0, 1, 0, -1};
    private static int dy[] = {1, 0, -1, 0};

    public static void main(String[] args) {
        input();
        System.out.println(playDummyGame());
    }

    private static void input() {
        Scanner sc = new Scanner(System.in);

        // 게임판 생성
        N = sc.nextInt();
        square = new int[N + 1][N + 1]; // 외곽을 표시하기 위해서 N + 1 사이즈로 정사각형 보드 생성

        // 사과 위치 저장
        K = sc.nextInt();
        for (int i = 0; i < K; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            square[x][y] = APPLE;
        }

        // 이동 전략 저장
        L = sc.nextInt();
        for (int i = 0; i < L; i++) {
            strategies.add(new Strategy(sc.nextInt(), sc.next().charAt(0)));
        }
    }

    private static int playDummyGame() {
        // 초기 뱀 위치 1,1  (0,0 은 외곽임)
        int x = 1;
        int y = 1;
        square[1][1] = SNAKE; // 현재는 뱀의 머리만 있음

        int direction = 0; // 처음 바라보는 방향은 동쪽
        int seconds = 0; // 경과 시간(초)
        int index = 0; // 다음에 회전할 정보

        Queue<Position> Q = new LinkedList<>();
        Q.offer(new Position(x, y));

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

            // 사각형 보드안에 존재하며, 뱀이 존재하는 위치가 아닐 경우
            if(isInSquare(nx, ny) && square[nx][ny] != SNAKE) {
                // 사과가 없으면 이동 후에 꼬리 제거
                if (square[nx][ny] != APPLE) {
                    square[nx][ny] = SNAKE;
                    Q.offer(new Position(nx, ny));

                    // 꼬리 제거 코드
                    Position prev = Q.poll();
                    square[prev.getX()][prev.getY()] = EMPTY;
                }
                // 사과가 있다면 이동 후에 꼬리 그대로 두기
                if (square[nx][ny] == APPLE) {
                    square[nx][ny] = SNAKE;
                    Q.offer(new Position(nx, ny));
                }
            } else { // 벽이나 뱀의 몸통과 부딪힌 경우
                seconds++;
                break;
            }

            // 다음 위치로 머리를 이동
            x = nx;
            y = ny;
            seconds++;
            if (index < L && seconds == strategies.get(index).getSeconds()) { // 회전할 시간인 경우 회전
                direction = turn(direction, strategies.get(index).getDirection());
                index += 1;
            }
        }
        return seconds;
    }

    // 사각형 보드안에 존재하는 경우
    private static boolean isInSquare(int x, int y) {
        return 1 <= x && x <= N && 1 <= y && y <= N;
    }

    // 회전
    public static int turn(int direction, char c) {
        if (c == 'L') {
            direction = (direction == 0) ? 3 : direction - 1;
        } else {
            direction = (direction + 1) % 4;
        }
        return direction;
    }
}