[알고리즘 - 구현] 뱀

☀️ 시작

풀다 풀다 안 풀려서 결국 답지를 보고 풀었던 문제.. 생각보다 간단했는데 처음에 했던 잘못된 접근법 하나에서 빠져나오지 못해 결국 풀지 못했다. 다음엔 오래 안 풀리는 문제는 며칠 뒤에 다시 도전해보는 것도 재밌을 것 같다.

📖 문제

문제 링크

먼저 문제는 뱀 게임을 시뮬레이션하는 문제로, 보드 위에서 움직이는 뱀이 벽에 닿거나 자신의 몸과 부딪히면 끝나는 게임의 종료까지 걸리는 시간을 계산하는 문제이다. 입력으로는 사과의 좌표와 방향 전환을 언제, 어떤 방향으로 해야하는지가 주어진다.

처음에는 문제를 잘못 이해해서 '방향 전환'이라는게 아래와 같이 방향 전환과 직진을 동시에 하는 건줄 알았는데

문제를 다시 잘 읽어보니 아래와 같이 n초 후에 뱀의 머리만 방향을 전환하는 것이었다. 즉, 4초 후에 기존에 생각했던 3초 후와 같은 상황이 만들어진다.

복잡해서 예제를 직접 따라가보지 않고 문제를 풀었더니 이런 일이 생겼다. 문제를 꼼꼼하게 읽자..!

🧑🏻‍💻 풀이

사과를 먹으면 뱀의 길이가 늘어나기 떄문에 여러 칸에 걸친 뱀의 움직임을 정확하게 시뮬레이션하는 것이 이 문제 풀이의 핵심이라고 할 수 있다.

첫번째 방법

처음에는 좌표 하나하나가 다음 위치를 계산해 움직여야 한다고 생각했다. 즉, 좌표 별로 큐를 가지고, 그 좌표들의 리스트를 만들어서 뱀이 이동할 때 마다 다음에 이동해야 할 정보를 각 좌표의 큐에 넣고 리스트 전체를 순회하는 방식이다.

이렇게 하면 안 되는것이, 그러면 계산해주어야 할 게 너무 많아진다. 좌표별로 현재의 방향을 가지고 있어야 하고, 큐에 언제 방향을 전환하는지 언제 직진하는지 등 정보를 가지고 있어야 한다. 또, 뱀이 직진할 때 마다 리스트의 모든 좌표에 정보를 넣어주어야 하고 '이동' 처리도 해주어야 한다.

처음엔 이 방법이 맞는줄알고 계속 풀다가 코드가 점점 산으로 가길래 영 아닌 것 같아서 다른 방법으로 풀었다.

두번째 방법

기존엔 좌표가 직접 다음 위치를 계산했다면, 이제는 뱀 전체가 하나가 되어 좌표를 계산하는 방법을 사용했다. 사실 문제에서 이미 방법을 제시하고 있었다.

이동 규칙의 3, 4번째를 보면 이동한 칸에 사과가 있다면 꼬리는 움직이지 않고, 사과가 없다면 꼬리가 줄어든다. 이를 그대로 코드에 녹여내면 문제가 풀린다.

Position (좌표)

static class Position {
    int x, y;

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

    // 주어진 dx, dy만큼 이동한 좌표 반환
    public Position movedPosition(int dx, int dy) {
        return new Position(x + dx, y + dy);
    }

    // 주어진 보드를 벗어났는지 확인
    public boolean isOutOfBound(int N) {
        return x < 1 || x > N || y < 1 || y > N;
    }

    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof Position)) {
            return false;
        }
        Position p = (Position) obj;
        return this.x == p.x && this.y == p.y;
    }
}

방향 정보 & 뱀 구성

방향의 경우, 뱀이 최초에 동쪽을 바라보고 있으며 (index : 0) 각각 좌측과 우측으로 회전하므로 index가 1 줄어들면 좌측으로 회전하고 1 증가하면 우측으로 회전하는 효과를 내도록 dx, dy 배열을 아래와 같이 구성해주었다.

// 방향 정보, 동쪽부터 시계방향 동/남/서/북
int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};

// 뱀 몸통
Deque<Position> snake = new LinkedList<>();

// 초기 위치, 방향 설정
int currentDirectionIndex = 0; // 0(동), 1(남), 2(서), 3(북)
snake.offer(new Position(1, 1));

꼬리 이동을 결정하는 코드

아래 코드에서 apples 는 각각 사과의 위치를 담고있는 List<Position\> 이다. 또한, snake Deque가 현재 몸통의 좌표 Position들을 가지고 있으므로 contains() 메서드로 새로운 머리가 몸통과 부딪히는지를 판단할 수 있다.

// 현재 뱀의 머리를 가져와 현재 방향대로 한 칸 이동
Position nextHead = snake.peekFirst().movedPosition(dx[currentDirectionIndex], dy[currentDirectionIndex]);

if (nextHead.isOutOfBound(N) || snake.contains(nextHead)) {
    // 벽이나 몸통과 부딪히는 경우
    break;
} else {
    // 부딪히지 않는 경우 
    snake.offerFirst(nextHead); // 먼저 머리 늘리기
    if (!apples.contains(nextHead)) {
        // 새로운 머리에 사과가 없으면 꼬리 하나 제거
        snake.pollLast();
    } else {
        // 사과가 있으면 사과 제거
        apples.remove(nextHead);
    }
}

위 코드처럼 무조건 새로운 좌표를 뱀의 머리에 추가하고(offerFirst()), 사과가 있다면 사과를 제거하고 사과가 없다면 꼬리를 제거해준다(pollLast()). 이렇게 하면 뱀 몸통의 움직임을 하나하나 계산해줄 필요 없이 뱀이 움직이고 증가하는대로 몸통이 속한 좌표를 정확히 유지할 수 있다.

그리고 마지막으로 이동을 완료한 후에 현재 시간에 방향 전환 지시가 있으면 방향을 전환해주면 된다. 문제에서 방향 전환은 'n초 후'에 이뤄진다고 했으므로 이동이 끝난 후에 뱀의 머리 방향을 틀어준다.

// 이동 완료 후 방향 전환이 있으면 수행
if (!rotations.isEmpty() && rotations.peek().time == time) {
    currentDirectionIndex = rotations.poll().nextDirectionIndex(currentDirectionIndex);
}

새로운 방향을 얻는 코드는 방향 전환에 대한 정보를 담는 Rotation 클래스에 작성해주었다.

Rotation

static class Rotation {
    int time;
    char direction;

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

    // Rotation이 갖고 있는 방향 전환 정보 direction('L' or 'D') 에 따라
    // 다음 directionIndex를 계산한다
    public int nextDirectionIndex(int currentDirectionIndex) {
        if (direction == 'L') {
            currentDirectionIndex--;
            if (currentDirectionIndex == -1) {
                return 3;
            }
        } else {
            currentDirectionIndex++;
            if (currentDirectionIndex == 4) {
                return 0;
            }
        }
        return currentDirectionIndex;
    }
}

뱀이 벽에 부딪히거나 몸통에 닿아 시뮬레이션이 끝나면 끝난 시점의 시간을 출력하면 된다. 몇 초 후에 게임이 종료되는지를 반환하는 것이므로 예를 들어 5초까지 정상 상태이다가 6초째 이동에서 게임이 종료되었다면 6초를 반환해주어야 하므로 time 변수는 이동이나 조건 검사 이전에 증가시켜주도록 작성했다.

전체 코드

github 링크