(C++) 3190번: 뱀

Standard

문제 링크: https://www.acmicpc.net/problem/3190

– 지도에서 0: 빈 곳, 1: 사과, 2: 몸 (머리 포함)으로 저장.
– 뱀의 몸 정보를 queue에 추가. (맨 뒤가 머리가 가도록 정보가 업데이트됨)
– 0부터 시작해서 주어진 방향으로 이동할 좌표 (nextHeadX, nextHeadY) 계산한 후, 벽돌에 부딪히는 경우나 이미 몸이 있는 경우 정지. 
– 이동할 곳에 사과가 있는 경우, 해당 장소를 map에서 2로 갱신하고 head 정보 업데이트. 몸 정보 업데이트.
– 이동할 곳에 사과가 없는 경우, 해당 장소를 2로 갱신, head 정보 갱신, 몸 정보 업데이트 (단 다른 점은 tail index (queue에서는 front)를 1 증가시킴))
– 이후 정해진 정보에 따라 방향 전환을 수행.

#include <iostream>

using namespace std;

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    // board size
    int numN = 0;
    cin >> numN;

    int map[numN][numN]; // 0: empty, 1: apple, 2: body
    for (int i = 0; i < numN; i++)
        for (int j = 0; j < numN; j++)
            map[i][j] = 0;

    // num of apple(s)
    int numK = 0;
    cin >> numK;

    for (int i = 0; i < numK; i++) {
        int tmpY = 0, tmpX = 0;
        cin >> tmpY;
        cin >> tmpX;

        map[tmpX - 1][tmpY - 1] = 1; // 1: apple
    }

    // num of direction change
    int numL = 0;
    cin >> numL;

    int changeAt[numL];
    char changeTo[numL];
    int currIdx = 0;

    for (int i = 0; i < numL; i++) {
        cin >> changeAt[i];
        cin >> changeTo[i];
    }   

    // current time, starting from 0
    int second = 0;
    int direction = 90; // up: 0, right: 90, down: 180, left: 270

    int snakeXList[numN * numN];
    int snakeYList[numN * numN];
    int headIdx = 0;
    int tailIdx = 0;

    snakeXList[headIdx] = 0;
    snakeYList[headIdx] = 0;

    map[snakeXList[headIdx]][snakeYList[headIdx]] = 2; // body

    while(true) {
        second++;

        int nextHeadX = 0;
        int nextHeadY = 0;

        switch (direction) {
            case 0:
                nextHeadX = snakeXList[headIdx];
                nextHeadY = snakeYList[headIdx] - 1;
                break;
            case 90:
                nextHeadX = snakeXList[headIdx] + 1;
                nextHeadY = snakeYList[headIdx];
                break;
            case 180:
                nextHeadX = snakeXList[headIdx];
                nextHeadY = snakeYList[headIdx] + 1;
                break;
            case 270:
                nextHeadX = snakeXList[headIdx] - 1;
                nextHeadY = snakeYList[headIdx];
                break;
        }

        // it it touches wall, finish
        if (nextHeadX == -1 || nextHeadX == numN || nextHeadY == -1 || nextHeadY == numN) {
            break;
        }

        // check next location
        if (map[nextHeadX][nextHeadY] == 2) {
            break;
        }
        else if (map[nextHeadX][nextHeadY] == 1) { // eat apple
            // just extend 
            headIdx++;
            snakeXList[headIdx] = nextHeadX;
            snakeYList[headIdx] = nextHeadY;

            map[snakeXList[headIdx]][snakeYList[headIdx]] = 2;
        }
        else { // no apple, just move
            map[snakeXList[tailIdx]][snakeYList[tailIdx]] = 0;
            tailIdx++; // increase tall index (to simplify process movement)

            headIdx++;
            snakeXList[headIdx] = nextHeadX;
            snakeYList[headIdx] = nextHeadY;

            map[snakeXList[headIdx]][snakeYList[headIdx]] = 2;
        }

        // has move information
        if (numL >= currIdx) {
            if (changeAt[currIdx] == second) {
                if (changeTo[currIdx] == 'L') {
                    direction -= 90;
                    if (direction < 0)
                        direction += 360;
                }
                else if (changeTo[currIdx] == 'D') {
                    direction += 90;
                    direction %= 360;
                }

                currIdx++;
            }
        }
    }

    cout << second;
}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.