이번에는 백준 3190번 뱀 문제를 풀어보았습니다.
뱀의 몸을 여러 개의 좌표로 관리하면서, 매초 머리를 한 칸 이동시키고 사과의 존재 여부에 따라 꼬리를 제거할지 결정해야 합니다.
또한 정해진 시간마다 방향을 회전시키고, 벽이나 자신의 몸에 부딪히는 순간 게임을 종료해야 하므로 덱을 이용한 시뮬레이션으로 해결하였습니다.
문제 설명
N × N 크기의 보드에서 뱀이 이동합니다.
처음 뱀은 (1,1)에 위치하며 길이는 1이고, 오른쪽을 바라보고 있습니다.
매초 다음 과정이 순서대로 진행됩니다.
- 머리를 현재 방향으로 한 칸 이동합니다.
- 벽이나 자신의 몸과 충돌하면 게임이 종료됩니다.
- 이동한 칸에 사과가 있다면 사과를 먹고 꼬리는 움직이지 않습니다.
- 사과가 없다면 꼬리를 한 칸 제거하여 몸의 길이를 유지합니다.
- 현재 시간이 방향 전환 시간이라면 왼쪽 또는 오른쪽으로 회전합니다.
게임이 시작된 뒤 몇 초 만에 종료되는지 구하는 문제입니다.
풀이 아이디어
뱀의 몸을 다음과 같은 덱에 저장하였습니다.
deque<pair<int, int>> snake;덱의 앞쪽에는 뱀의 머리를 저장하고, 뒤쪽에는 뱀의 꼬리를 저장합니다.
뱀이 이동할 때마다 새로운 머리 좌표를 push_front()로 추가합니다.
사과를 먹지 않았다면 몸의 길이가 유지되어야 하므로 pop_back()으로 꼬리를 제거합니다.
사과를 먹었다면 꼬리를 제거하지 않아 뱀의 길이가 1 증가합니다.
방향은 오른쪽, 아래, 왼쪽, 위 순서로 저장한 방향 배열과 모듈러 연산을 사용하여 관리하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
// (0,1), (1,0), (0, -1), (-1,0)
int dy[4] = {0,1,0,-1};
int dx[4] = {1,0,-1,0};
int N;
int num;
vector<pair<int, int>> apple;
vector<pair<int, char>> direction_change;
deque<pair<int, int>> snake;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
cin >> num;
for (int i=0; i<num; i++) {
int y,x;
cin >> y >> x;
apple.push_back({y-1,x-1});
}
cin >> num;
for (int i=0; i<num; i++) {
int t;
char direction;
cin >> t >> direction;
direction_change.push_back({t, direction});
}
int t=0;
int d_index=0;
snake.push_front({0,0});
bool break_flag = false;
bool eat_apple = false;
while(true) {
t++;
auto[y,x] = snake.front();
int ny = y + dy[d_index];
int nx = x + dx[d_index];
if (ny < 0 || nx < 0 || ny > N-1 || nx > N-1) {
break_flag = true;
}
for (auto [ty, tx] : snake) {
if (ty == ny && tx == nx){
break_flag = true;
}
}
if (break_flag) break;
for (auto &[ay, ax] : apple) {
if (ay == ny && ax == nx) {
eat_apple = true;
ay = -1;
ax = -1;
break;
}
}
snake.push_front({ny,nx});
if (!eat_apple) {
snake.pop_back();
} else {
eat_apple = false;
}
for (auto [time,direct] : direction_change) {
if (time == t) {
if (direct == 'L') {
d_index = (d_index + 3) % 4;
}
if (direct == 'D') {
d_index = (d_index + 1) % 4;
}
}
}
}
cout << t;
return 0;
}풀이 흐름
-
보드의 크기와 사과의 위치를 입력받습니다.
-
방향 전환 시간과 회전 방향을 입력받습니다.
-
뱀의 시작 위치
(0,0)을 덱에 저장합니다. -
매초 현재 머리 위치에서 진행 방향으로 다음 좌표를 계산합니다.
-
다음 좌표가 보드를 벗어나거나 뱀의 몸과 겹치는지 확인합니다.
-
충돌하면 현재 시간을 출력하기 위해 반복문을 종료합니다.
-
다음 위치에 사과가 있는지 확인합니다.
-
새로운 머리 위치를 덱의 앞쪽에 추가합니다.
-
사과를 먹지 않았다면 덱의 뒤쪽에서 꼬리를 제거합니다.
-
현재 시간이 방향 전환 시간이라면 방향을 변경합니다.
-
충돌이 발생할 때까지 위 과정을 반복합니다.
구현 포인트
1. 뱀의 몸을 덱으로 관리
deque<pair<int, int>> snake;뱀은 머리와 꼬리 양쪽에서 작업이 필요합니다.
- 머리 추가: 앞쪽
- 꼬리 제거: 뒤쪽
따라서 앞뒤 삽입과 삭제가 모두 가능한 deque를 사용하였습니다.
덱에서
snake.front()는 현재 뱀의 머리이고,
snake.back()은 현재 뱀의 꼬리입니다.
2. 뱀의 시작 상태
int t=0;
int d_index=0;
snake.push_front({0,0});문제의 좌표는 1부터 시작하지만 코드에서는 0부터 시작하도록 변환하였습니다.
따라서 처음 위치인 (1,1)은 코드에서 (0,0)이 됩니다.
처음 방향은 오른쪽이므로 d_index를 0으로 설정하였습니다.
3. 방향 배열 구성
int dy[4] = {0,1,0,-1};
int dx[4] = {1,0,-1,0};각 인덱스는 다음 방향을 나타냅니다.
0: 오른쪽
1: 아래
2: 왼쪽
3: 위방향을 시계 방향 순서로 저장하였기 때문에 모듈러 연산으로 쉽게 회전시킬 수 있습니다.
4. 다음 머리 위치 계산
auto[y,x] = snake.front();
int ny = y + dy[d_index];
int nx = x + dx[d_index];현재 뱀의 머리 좌표를 가져온 뒤, 현재 방향에 해당하는 dy, dx 값을 더하여 다음 위치를 계산합니다.
매초 먼저 머리가 한 칸 이동해야 하므로 시간 t를 증가시킨 뒤 다음 좌표를 구합니다.
t++;5. 벽과의 충돌 확인
if (ny < 0 || nx < 0 || ny > N-1 || nx > N-1) {
break_flag = true;
}다음 머리 위치가 보드 범위를 벗어나면 벽에 부딪힌 것입니다.
이 경우 게임이 즉시 종료됩니다.
6. 자기 몸과의 충돌 확인
for (auto [ty, tx] : snake) {
if (ty == ny && tx == nx){
break_flag = true;
}
}현재 뱀의 몸에 해당하는 모든 좌표를 순회하면서 다음 머리 위치와 같은 좌표가 있는지 확인합니다.
같은 좌표가 존재한다면 뱀이 자신의 몸과 충돌한 것이므로 게임을 종료합니다.
if (break_flag) break;벽 또는 몸과 충돌한 경우에는 머리를 실제로 추가하지 않고 바로 반복문을 종료합니다.
7. 사과 위치 저장
vector<pair<int, int>> apple;입력으로 받은 사과의 위치를 벡터에 저장하였습니다.
문제의 좌표는 1부터 시작하므로 입력받을 때 1을 빼서 0부터 시작하는 좌표로 변환합니다.
apple.push_back({y-1,x-1});8. 사과 먹기
for (auto &[ay, ax] : apple) {
if (ay == ny && ax == nx) {
eat_apple = true;
ay = -1;
ax = -1;
break;
}
}새로운 머리 위치와 사과의 위치가 같다면 사과를 먹은 것입니다.
eat_apple을 true로 변경하고, 해당 사과의 좌표를 (-1,-1)로 바꾸어 다시 먹지 못하도록 처리하였습니다.
참조 구조 분해를 사용했기 때문에
auto &[ay, ax]에서 ay, ax를 수정하면 실제 apple 벡터의 값도 변경됩니다.
9. 머리 추가와 꼬리 제거
새로운 머리 위치를 덱의 앞쪽에 추가합니다.
snake.push_front({ny,nx});사과를 먹지 않았다면 기존 몸의 길이를 유지해야 하므로 꼬리를 제거합니다.
if (!eat_apple) {
snake.pop_back();
}사과를 먹었다면 꼬리를 제거하지 않습니다.
else {
eat_apple = false;
}따라서 덱에 저장된 좌표의 개수가 하나 늘어나면서 뱀의 길이도 1 증가합니다.
10. 방향 전환 시점
문제에서는 X초가 끝난 뒤에 방향을 회전한다고 하였습니다.
따라서 다음 순서로 처리해야 합니다.
- 머리 이동
- 충돌 검사
- 사과 처리
- 꼬리 이동
- 방향 전환
코드에서도 뱀의 이동 처리가 모두 끝난 뒤 방향을 변경합니다.
for (auto [time,direct] : direction_change) {
if (time == t) {현재 시간 t와 방향 전환 시간이 같을 때 회전합니다.
11. 오른쪽 회전
if (direct == 'D') {
d_index = (d_index + 1) % 4;
}방향 배열이 오른쪽, 아래, 왼쪽, 위의 시계 방향 순서로 저장되어 있습니다.
따라서 오른쪽으로 90도 회전하려면 인덱스를 1 증가시키면 됩니다.
예를 들어 다음과 같이 변경됩니다.
오른쪽(0) → 아래(1)
아래(1) → 왼쪽(2)
왼쪽(2) → 위(3)
위(3) → 오른쪽(0)인덱스가 3에서 4가 되는 경우를 다시 0으로 만들기 위해 % 4를 사용합니다.
12. 왼쪽 회전
if (direct == 'L') {
d_index = (d_index + 3) % 4;
}왼쪽 회전은 현재 방향 인덱스에서 1을 빼는 것과 같습니다.
하지만 d_index가 0일 때 단순히 1을 빼면 음수가 됩니다.
따라서 4를 더한 뒤 1을 빼는 것과 같은
d_index + 3을 사용합니다.
예를 들어 다음과 같이 변경됩니다.
오른쪽(0) → 위(3)
위(3) → 왼쪽(2)
왼쪽(2) → 아래(1)
아래(1) → 오른쪽(0)13. 게임 종료 시간
t++;매 반복문의 시작에서 시간을 먼저 1초 증가시킵니다.
이후 이동하려는 위치가 벽이나 자신의 몸이라면 해당 초에 충돌한 것입니다.
따라서 반복문을 종료한 뒤 현재 시간 t를 그대로 출력합니다.
cout << t;14. 시뮬레이션 문제에서 중요한 순서
이 문제에서는 각 행동의 순서가 중요합니다.
특히 방향 전환은 이동하기 전에 하는 것이 아니라, 해당 초의 이동이 끝난 뒤 수행해야 합니다.
또한 충돌 검사는 새로운 머리를 덱에 추가하기 전에 확인해야 합니다.
코드에서는 다음 순서를 그대로 구현하였습니다.
시간 증가
→ 다음 머리 위치 계산
→ 충돌 검사
→ 사과 확인
→ 머리 추가
→ 필요하면 꼬리 제거
→ 방향 전환이 순서를 다르게 구현하면 방향이 한 초 일찍 바뀌거나, 충돌 시점이 달라질 수 있습니다.
15. 시간복잡도
매초 자기 몸과의 충돌 여부를 확인하기 위해 현재 뱀의 전체 몸을 순회합니다.
또한 사과와 방향 전환 정보를 벡터에서 순회합니다.
뱀의 최대 길이와 사과 및 방향 전환 횟수는 모두 제한되어 있으므로 충분히 해결할 수 있습니다.
코드의 전체 시간복잡도는 게임이 진행된 시간을 S라고 할 때 대략 다음과 같습니다.
O(S × (뱀의 길이 + K + L))문제의 입력 범위에서는 충분히 통과할 수 있습니다.
