Computer Science & Engineering

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

이 문제는 정답 비율에 비해 쉽게 구현할 수 있는 문제이다. 문제는 간단하다. 뱀이 이동하며 사과를 먹으면 몸의 길이가 늘어난다. 문제에 설명이 부족하여 헷갈렸지만 1초에 1칸씩 움직인다고 생각하면 된다.

풀이

    이 문제는 방향성을 가지고 있는 문제이다. 현재 진행 방향에서 좌회전하냐 우회전하냐의 문제를 쉽게 구현하기 위하여 아래와 같이 방향을 나타내는 배열을 이용하였다. dx, dy의 인덱스 값을 1 올릴 때마다 시계 방향으로 회전하고 반대로 1 내릴 때마다 반시계 방향으로 회전한다.

int dx[4] = {-1, 0, 1, 0}; //상, 우, 하, 좌 : 시계방향
int dy[4] = {0, 1, 0, -1};

    뱀을 나타내기 위하여 앞 뒤로 좌표를 넣어야한다는 점에 딱 맞은 deque를 이용해야겠다고 생각했다. deque의 front는 뱀의 머리를, back은 뱀의 꼬리를 나타낸다. NxN 보드에서 1인 점은 사과가 있는 지점이고 -1인 곳은 뱀이 차지하고 있는 곳이다. 알고리즘은 다음과 같이 동작한다.

1. 만약 머리가 향하는 다음 지점이 보드를 벗어날 경우 게임이 끝난지를 판단하는 fin변수를 true로 바꾸고 게임을 종료한다.
2. 뱀을 나타내는 deque에 다음 지점의 좌표를 push_front하여 머리를 갱신해준다.
3. 그렇지 않은 경우 만약 머리가 향하는 다음 지점에 사과가 없을 경우 꼬리부분을 pop_back하고 -1이었던 꼬리부분을 0으로 바꾸어준다.
4. 그 다음 머리가 향한 다음 지점이 -1인 경우, 즉 뱀의 몸통을 만난 경우 fin변수를 true로 바꾸고 게임을 종료한다.
5. 뱀의 머리가 향하는 다음 지점을 -1로 바꾼다.
6. 왼쪽으로 회전하는 경우 방향을 나타내는 변수에 3을 더하고 4로 나눈 나머지를 다음 방향으로 정한다.
7. 오른쪽으로 회전하는 경우 방향을 나타내는 변수에 1을 더하고 4로 나눈 나머지를 다음 방향으로 정한다.
8. 방향을 모두 바꾼 다음에도 종료되지 않은 경우 벽을 만날 때까지 직진한다.

소스 코드

#include <iostream>
#include <cstring>
#include <vector>
#include <deque>

using namespace std;

int arr[101][101]; //보드 배열

int N, K, L;

int dx[4] = {-1, 0, 1, 0}; //상, 우, 하, 좌 : 시계방향
int dy[4] = {0, 1, 0, -1};

deque<pair<int,int>> snake; //뱀을 나타내는 deque
vector<pair<int,char>> info; //이동 시간과 위치 저장 벡터

int main() {
    bool fin = false; //게임이 끝난지 판단하는 변수
    int direction = 1; //현재 방향(오른쪽)
    int answer = 0; //정답
    int time = 0; //시간
    snake.push_front({1, 1}); //현재 위치 뱀에 추가
    arr[1][1] = -1; //뱀이 현재 있는 곳 표시
    cin >> N >> K; //입력
    for(int i = 0; i < K; i++) {
        int a, b; cin >> a >> b;
        arr[a][b] = 1;
    }
    cin >> L;
    for(int i = 0; i < L; i++) {
        int x; char c; cin >> x >> c;
        info.push_back({x - time, c});
        time = x;
    }
    for(pair<int, char> e : info) {
        int x = e.first; //시간
        char c = e.second; //다음 방향
        while(!fin && x--) {
            answer++;  //시간 증가
            int nx = snake.front().first + dx[direction]; //다음 x, y 좌표
            int ny = snake.front().second + dy[direction];
            if(nx < 1 || nx > N || ny < 1 || ny > N) { //벽에 닿은 경우 종료
                fin = true;
                break;
            }
            snake.push_front({nx, ny}); //뱀의 머리 갱신
            if(arr[nx][ny] == 0) { //사과가 없는 경우
                pair<int,int> back = snake.back(); //꼬리 제거
                snake.pop_back();
                arr[back.first][back.second] = 0; //보드에서 삭제
            }
            if(arr[nx][ny] == -1) { //뱀의 몸통을 만난 경우
                fin = true; //게임 종료
                break;
            }
            arr[nx][ny] = -1; //뱀의 머리 보드에 체크
        }

        if(c == 'L') //왼쪽으로 회전하는 경우
            direction += 3;
        else //오른쪽으로 회전하는 경우
            direction++;

        direction %= 4; //4개의 원소가 있으므로 범위를 벗어나지 않고 회전하게 만듦
    }
    while(!fin) { //방향 조절이 끝난 후 벽에 부딪힐 때까지 직진
        answer++; 
        int nx = snake.front().first + dx[direction]; //다음 x, y 좌표
        int ny = snake.front().second + dy[direction];
        if(nx < 1 || nx > N || ny < 1 || ny > N) { //벽에 부딪힌 경우 종료
            fin = true;
            break;
        }
        snake.push_front({nx, ny}); //머리 갱신
        if(arr[nx][ny] == 0) { //사과가 없는 경우
            pair<int,int> back = snake.back(); //꼬리 제거
            snake.pop_back();
            arr[back.first][back.second] = 0;
        }
        if(arr[nx][ny] == -1) { //몸통을 만난 경우 종료
            fin = true;
            break;
        }
        arr[nx][ny] = -1; //뱀이 있으므로 체크
    }

    cout << answer; //정답 출력
}

위의 풀이를 코드로 구현한 결과이다.

채점 결과