[백준] 3190: 뱀 (C++)

Recent Posts

Recent Comments

Link

« 2026/05 »
일	월	화	수	목	금	토
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31

Tags more

Archives

Today | Total

관리 메뉴

Bull

[백준] 3190: 뱀 (C++) 본문

Algorithm/Baekjoon

[백준] 3190: 뱀 (C++)

Bull_ 2026. 3. 10. 05:02

3190: 뱀
10875: 뱀 (Advanced)

문제

보드 위에 뱀이 돌아 다닌다. 초기 길이가 1인데, 사과를 먹으면 길이가 늘어난다. 벽이나 자기 자신의 몸에 부딪치면 종료된다. 이 때 몇 번 움직였는지 출력하면 된다. 출발점은(1, 1)로 시작되며, 전체 좌표는 `1-based index`로 주어진다. 뱀은 회전할 수 있는데 x 번째에 `D`가 주어지면 오른쪽, `L`이 주어지면 왼쪽으로 90°돌릴 수 있다. 해당 포스트는 3190번 문제를 다루지만 비슷한 내용에 똑같은 제목으로 10875번도 있다. 10875번 문제는 단순 구현으로 하게 되면 `메모리 초과`가 나오므로 이 문제의 다음 단계로 풀면 좋을 것 같다.

분석

우선 이 문제는 구현만 하면 된다. 하지만 설계를 어떻게 할 지 잘 생각해야 한다. 뱀은 어떻게 움직이게 정의할 것 인가? 보드의 상태로 매번 $N \times N$을 계속 업데이트할 것 인가? 여러 방법이 있겠지만, 가장 기본적인 방법은 뱀을 `Deque`에 넣는다. 뱀이 움직일 때 마다 다음 좌표에 올 머리 정보를 넣고, 꼬리의 정보는 빼내는 것이다. deque는 queue의 형태에서 양방향으로 push & pop이 가능하다.

그리고 뱀은 한 방향으로만 움직이는데, 특정 시간마다 뱀의 방향을 바꿀 수 있다. 그래서 뱀은 방향을 기억해놔야 한다. 방향을 바꾸는 시점에서 방향을 우선 돌리고 다음 칸으로 움직여야 한다.

뱀의 상태는 다음과 같이 구조체로 만들 수 있다.

enum class Direction { EAST, SOUTH, WEST, NORTH };

struct Pos {
    int r;
    int c;
};

struct Snake {
    deque<Pos> p;
    Direction d;
};

방향의 정의도 중요하다. 아래로 간다는 건, 좌표를 기준으로 위로 가는 건지? 아래로 가는 건지? 많이 헷갈릴 수 있다. 이때 문제를 잘 살펴봐야한다. 문제에 적혀있기를, "뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다."

맨 위, 맨 좌측, 오른쪽으로 향한다. 맨 좌측이라는 건, 좌측에 더 이상 공간이 없음을 의미하고 오른쪽 방향으로 진행되니까 오른쪽(EAST)은 증가하는 방향이고, 맨 위라는 건, 위쪽에 더 이상 공간이 없음을 의미하므로, 아래 방향(SOUTH)가 증가하는 방향이 된다.

이를 코드로 표현하면 다음과 같다. 우리가 볼 때 그림은 아래방향이지만 숫자는 증가하도록 하였다.

Pos next_pos(Pos head, Direction d) {
    switch (d) {
    case Direction::EAST:
        head.c++;
        break;
    case Direction::SOUTH:
        head.r++;
        break;
    case Direction::WEST:
        head.c--;
        break;
    case Direction::NORTH:
        head.r--;
        break;
    default:
        break;
    }
    return head;
}

뱀은 맨 처음에 1칸을 차지하면서 움직이는데, 만약 사과를 먹게 되면 뱀의 길이가 1칸 늘어난다. 문제에서는, 사과를 먹으면 머리가 생기고 꼬리가 사라지지 않는다라는 표현을 사용했다. 즉, `deque`를 통해 평소에는 다음 머리 위치를 구하고 deque에 push한 뒤, 꼬리쪽은 pop해주는 것인데, 사과를 먹으면 머리 위치를 push하지만 꼬리는 pop을 하지 않는다.

↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓

이를 코드로 표현하면 다음과 같다.

auto old_head = snake.p.front();
snake.p.push_front(next_pos(old_head, snake.d));
auto new_head = snake.p.front();

snake.p.pop_back();

위와 같은 중요한 몇 가지 사항만 알고 있으면 나머지는 큰 어려움 없이 해결할 수 있다.

뱀이 기어가는 전체적인 프로세스는 다음과 같다.

(1, 1)과 EAST 방향으로 초기화하고 충돌이 나올 때 까지 반복한다.
방향 전환의 정보를 queue에 기록하고 매 턴마다 유효한지 확인하다.
턴(시간)을 증가시킨다.
새로운 머리를 업데이트한다.
충돌이 있는지 확인한다. (뱀의 몸, 벽)
사과가 있는지 확인한다. 사과는 List에 저장하고 매 턴 마다 해당 List를 순회하며 검사한다. 만약 사과가 있다면 꼬리를 pop하지 않는다.

필요한 핵심 함수는 다음과 같다.

void crawl();
bool is_collision(const Snake &s);
Pos next_pos(Pos head, Direction d);

Direction rotate90(Direction &d);
Direction irotate90(Direction &d);

1. 초기화

struct Snake {
    deque<Pos> p;
    Direction d;
};

Snake snake;

void crawl() {
    // 1. 초기화
    snake.p.push_back({1, 1});
    snake.d = Direction::EAST;
    
    // ...
}

문제의 내용처럼 (1, 1)로 시작하고 오른쪽(동쪽)방향의 상태를 입력해준다.

2. 방향 검사

void crawl() {
    // 1. 초기화
    snake.p.push_back({1, 1});
    snake.d = Direction::EAST;

    while (true) {
        // print_state();
        // 2. 방향 검사
        if (!cond.empty() && x == cond.front().t) {
            if (cond.front().r == 'L') {
                snake.d = irotate90(snake.d);
            }
            if (cond.front().r == 'D') {
                snake.d = rotate90(snake.d);
            }
            cond.pop();
        }
        x++;
        // ...
    }
}

`irotate90()`, `rotate90()`은 다음과 같다.

enum class Direction { EAST, SOUTH, WEST, NORTH };

Direction rotate90(Direction &d) {
    int val = (static_cast<int>(d) + 1) % 4;
    d = static_cast<Direction>(val);
    return d;
}

Direction irotate90(Direction &d) {
    int val = (static_cast<int>(d) - 1 + 4) % 4;
    d = static_cast<Direction>(val);
    return d;
}

`Direction`는 열거형 클래스 enum class 예약어로 정의하였다. 0번째(`EAST`) 기준으로 시계방향으로 90도를 꺾으면 `SOUTH`가 된다. 모듈로 연산을 통해 순회하도록 만들었다. `EAST`를 반시계방향으로 돌리면 `NORTH`가 된다. 음수가 나오지 않게 (-1 + 4)를 더하여 반대방향으로 순회할 수 있도록 만들어 주었다.

3. 머리 업데이트

void crawl() {
    // 1. 초기화
    snake.p.push_back({1, 1});
    snake.d = Direction::EAST;

    while (true) {
        // print_state();
        // 2. 방향 검사
        if (!cond.empty() && x == cond.front().t) {
            if (cond.front().r == 'L') {
                snake.d = irotate90(snake.d);
            }
            if (cond.front().r == 'D') {
                snake.d = rotate90(snake.d);
            }
            cond.pop();
        }
        x++;

        // 3. 머리 업데이트
        auto old_head = snake.p.front();
        snake.p.push_front(next_pos(old_head, snake.d));
        auto new_head = snake.p.front();
		// ...
    }
}

머리를 deque의 front로 정의하였기 때문에 앞부분을 가져와 `next_pos()`에 넣어 새로운 머리 위치를 가져온다.

4. 충돌 검사

void crawl() {
    // 1. 초기화
    snake.p.push_back({1, 1});
    snake.d = Direction::EAST;

    while (true) {
        // print_state();
        // 2. 방향 검사
        if (!cond.empty() && x == cond.front().t) {
            if (cond.front().r == 'L') {
                snake.d = irotate90(snake.d);
            }
            if (cond.front().r == 'D') {
                snake.d = rotate90(snake.d);
            }
            cond.pop();
        }
        x++;

        // 3. 머리 업데이트
        auto old_head = snake.p.front();
        snake.p.push_front(next_pos(old_head, snake.d));
        auto new_head = snake.p.front();

        // 4. 충돌 검사
        if (is_collision(snake)) {
            break;
        }
        // ...
    }
}

뱀의 길이가 늘어난 직후이므로 바로 충돌 검사를 해주어야 한다. `is_collision()`은 벽, 뱀의 몸통에 부딪히는 지 2가지 확인해주면 된다.

bool is_collision(const Snake &s) {
    deque<Pos> snake = s.p;
    Pos p = snake.front();

    if (p.r >= N + 1 || p.c >= N + 1 || p.r < 1 || p.c < 1) {
        return true;
    }
    for (int i = 1; i < snake.size(); i++) {
        if (snake[i].r == p.r && snake[i].c == p.c) {
            return true;
        }
    }
    return false;
}

`1-based index` 였다는 것을 상기하자. 뱀의 머리는 몸통과의 충돌이 있는지 모두 검사해야 한다.

5. 사과 확인

void crawl() {
    // 1. 초기화
    snake.p.push_back({1, 1});
    snake.d = Direction::EAST;

    while (true) {
        // print_state();
        // 2. 방향 검사
        if (!cond.empty() && x == cond.front().t) {
            if (cond.front().r == 'L') {
                snake.d = irotate90(snake.d);
            }
            if (cond.front().r == 'D') {
                snake.d = rotate90(snake.d);
            }
            cond.pop();
        }
        x++;

        // 3. 머리 업데이트
        auto old_head = snake.p.front();
        snake.p.push_front(next_pos(old_head, snake.d));
        auto new_head = snake.p.front();

        // 4. 충돌 검사
        if (is_collision(snake)) {
            break;
        }

        // 5. 사과 확인
        bool is_apple = 0;
        for (auto &apple : apples) {
            if (new_head.r == apple.r && new_head.c == apple.c) {
                apple.r = apple.c = 0;
                is_apple = 1;
                break;
            }
        }
        
        if (is_apple)
            continue;

        snake.p.pop_back();
    }
}

사과는 입력 정보에서 위치에 순서가 없기 때문에 List에 넣어주고 매번 모두 검사해야한다. 새로운 머리에 사과가 있는지 검사하고, 있으면 해당 사과는 제거해줄 수도 있지만, (0, 0) 위치는 갈 일이 없기 때문에 `없음` 의 대체 표시 방법이다. `is_apple` 변수를 통해 뱀의 꼬리를 pop 할지 말지 분기시킬 수 있다.

이 과정을 콘솔에 시각화하면 다음과 같다.

전체 코드

#include <deque>
#include <iostream>
#include <queue>
#include <time.h>
#include <vector>

enum class Direction { EAST, SOUTH, WEST, NORTH };
using namespace std;

struct Pos {
    int r;
    int c;
};

struct Condition {
    int t;
    char r;
};

struct Snake {
    deque<Pos> p;
    Direction d;
};

int N, K, L;
vector<vector<int>> board;
vector<Pos> apples;
queue<Condition> cond;
Snake snake;

int x = 0;

void input();
void output();
void solve();
void print_state();

void crawl();
bool is_collision(const Snake &s);
Pos next_pos(Pos head, Direction d);

Direction rotate90(Direction &d);
Direction irotate90(Direction &d);

void crawl() {
    // 1. 초기화
    snake.p.push_back({1, 1});
    snake.d = Direction::EAST;

    while (true) {
        // print_state();
        // 2. 방향 검사
        if (!cond.empty() && x == cond.front().t) {
            if (cond.front().r == 'L') {
                snake.d = irotate90(snake.d);
            }
            if (cond.front().r == 'D') {
                snake.d = rotate90(snake.d);
            }
            cond.pop();
        }
        x++;

        // 3. 머리 업데이트
        auto old_head = snake.p.front();
        snake.p.push_front(next_pos(old_head, snake.d));
        auto new_head = snake.p.front();

        // 4. 충돌 검사
        if (is_collision(snake)) {
            break;
        }

        // 5. 사과 확인
        bool is_apple = 0;
        for (auto &apple : apples) {
            if (new_head.r == apple.r && new_head.c == apple.c) {
                apple.r = apple.c = 0;
                is_apple = 1;
                break;
            }
        }

        if (is_apple)
            continue;

        snake.p.pop_back();
    }
}

bool is_collision(const Snake &s) {
    deque<Pos> snake = s.p;
    Pos p = snake.front();

    if (p.r >= N + 1 || p.c >= N + 1 || p.r < 1 || p.c < 1) {
        return true;
    }
    for (int i = 1; i < snake.size(); i++) {
        if (snake[i].r == p.r && snake[i].c == p.c) {
            return true;
        }
    }
    return false;
}

Pos next_pos(Pos head, Direction d) {
    switch (d) {
    case Direction::EAST:
        head.c++;
        break;
    case Direction::SOUTH:
        head.r++;
        break;
    case Direction::WEST:
        head.c--;
        break;
    case Direction::NORTH:
        head.r--;
        break;
    default:
        break;
    }
    return head;
}

Direction rotate90(Direction &d) {
    int val = (static_cast<int>(d) + 1) % 4;
    d = static_cast<Direction>(val);
    return d;
}

Direction irotate90(Direction &d) {
    int val = (static_cast<int>(d) - 1 + 4) % 4;
    d = static_cast<Direction>(val);
    return d;
}

void input() {
    cin >> N;
    cin >> K;
    board.assign(N + 1, vector<int>(N + 1, 0));
    apples.assign(K, {0, 0});
    for (int i = 0; i < K; i++) {
        cin >> apples[i].r >> apples[i].c;
    }
    cin >> L;

    for (int i = 0; i < L; i++) {
        int t;
        char c;
        cin >> t >> c;
        cond.push({t, c});
    }
}

void output() {
    cout << x;
    cout << endl;
}

void print_state() {
    auto apples_copy = apples;
    auto snake_copy = snake.p;
    vector<vector<char>> board_copy;
    board_copy.assign(N + 1, vector<char>(N + 1, '#'));

    for (auto &apple : apples_copy) {
        if (apple.r == 0) {
            continue;
        }
        board_copy[apple.r][apple.c] = 'a';
        apple.r = apple.c = 0;
    }

    for (auto &s : snake_copy) {
        board_copy[s.r][s.c] = 's';
    }
    printf("===\n");
    for (int r = 1; r <= N; r++) {
        for (int c = 1; c <= N; c++) {
            printf("%c", board_copy[r][c]);
        }
        printf("\n");
    }
    printf("===\n");
}

void solve() {
    input();
    crawl();
    output();
}

int main() {
    solve();
    return 0;
}

Insight

`struct`를 응용하면 복잡하지 않게 시물레이션할 수 있는 문제였다.
문제의 방향 정의를 파악하고 설계해야 한다. 또한 반대 방향 전환시 `-` 쪽으로 모듈로 연산하는 것을 익혀 놓으면 좋다.
`crawl()`에서 각각의 프로세스들을 어떤 위치에서 할 지 정할 수 있어야 한다. 예를들어 `is_collision()`은 새로운 `head`가 생겼기 때문에 직후 바로 충돌 검사를 해야한다.

참고자료

Google. [AI] Gemini: Google의 AI 협업 도구 및 대규모 언어 모델. https://gemini.google.com/

'Algorithm > Baekjoon' 카테고리의 다른 글

[백준] 12100: 2048_Easy (C++) (0)	2026.03.09
[백준] 1019: 책 페이지 (C++) (1)	2024.09.22
[백준] 2143: 두 배열의 합 (C++) (10)	2024.07.22
[백준] 1806: 부분합 (C++) (0)	2024.07.20
[백준] 13913: 숨바꼭질 4 (C++) (0)	2024.05.19

'Algorithm/Baekjoon' Related Articles

Bull

[백준] 3190: 뱀 (C++) 본문

[백준] 3190: 뱀 (C++)

문제

분석

Insight

참고자료

'Algorithm > Baekjoon' 카테고리의 다른 글

티스토리툴바