C - [백준 3190] 뱀 (feat. 시뮬레이션)

참고 포스트

 

2025.01.09 - [Computer Science/자료구조 & 알고리즘] - [알고리즘] 시뮬레이션 문제는 왜 어려울까? (feat. 설계의 중요성)

[알고리즘] 시뮬레이션 문제는 왜 어려울까? (feat. 설계의 중요성)

 

 

 

 

백준 3190번 뱀 (https://www.acmicpc.net/problem/3190): 

문제 요약

뱀 게임을 시뮬레이션하는 문제입니다. 뱀은 2차원 평면에서 이동하며, 다음 조건을 충족해야 합니다:

1. 이동한 칸에 사과가 있다면:
   • 사과를 먹고 길이가 증가.
2. 이동한 칸에 사과가 없다면:
   • 길이 증가 없이 이동.
3. 맵 경계를 넘어가거나, 자기 몸에 충돌하면 게임 종료.

게임 종료 시점의 시간을 출력해야 합니다.

---

입력 설명

1. 첫 줄: 맵의 크기 N (2 ≤ N ≤ 100)
2. 둘째 줄: 사과의 개수 K (0 ≤ K ≤ 100)
3. 다음 K줄: 사과의 위치 (행, 열)
4. 그다음 줄: 방향 전환 횟수 L (1 ≤ L ≤ 100)
5. 다음 L줄: 방향 전환 정보 (초, 방향)
   • 방향: 'L' (왼쪽 회전), 'D' (오른쪽 회전)

---

출력 설명

• 게임 종료 시점의 시간을 출력합니다.

---

Checkpoint

 

방향 전환에 대한 처리와 게임이 끝나는 조건을 처리하는 방법에 대해 익숙하다면 알고리즘을 처리하는데 크게 어려움이 없습니다.

 

다른 방향전환 문제 - BOJ_14503_로봇청소기

 

2025.01.09 - [Computer Science/알고리즘 문제] - C - 백준 14503 로봇 청소기 (feat. 시뮬레이션, 재귀)

 

처음에 재귀로 설계하였다가, 굳이 스택을 쌓을 필요가 없다고 생각하여 while 반복문으로 변경하였습니다.

 

---

구현 코드

/*
C_BOJ_3190 뱀
https://www.acmicpc.net/problem/3190

Keypoint

만약 이동한 칸에 사과가 있다면, 
그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.

만약 이동한 칸에 사과가 없다면, 
몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

1. 맵 크기 입력받기 > 사과 배치하기

2. 뱀이동 시키기

*/
#include <stdio.h>

// 입력값
int N = 0; // 맵 크기
int K = 0; // 사과 개수
int L = 0; // 방향 전환 횟수

// 게임 세팅
int map[100][100] = {0};
int action_time[100] = {0};
char action_cmd[100] = {0};
int dir_x[4] = {0, 1, 0, -1}; // 오른쪽, 아래, 왼쪽, 위
int dir_y[4] = {1, 0, -1, 0};

// 초기값
int snake[10000][2];
int front = 0, rear = 0; // 큐의 앞과 뒤
int snake_dir = 0;       // 초기 방향: 오른쪽
int phase = 0;           // 방향 전환 단계
int time = 0;            // 게임 시간

// 큐 삽입 (뱀 길이 증가)
void enqueue(int x, int y) {
    snake[rear][0] = x;
    snake[rear][1] = y;
    rear++;
}

// 큐 삭제 (뱀 길이 감소)
void dequeue() {
    front++;
}

// 게임 진행 함수
void game() {
    int x = 0, y = 0; // 뱀의 초기 위치
    enqueue(x, y);    // 초기 뱀 위치 저장

    while (1) {
        // 방향 전환 처리
        if (phase < L && time == action_time[phase]) {
            if (action_cmd[phase] == 'L') {
                snake_dir = (snake_dir + 3) % 4; // 왼쪽 회전
            } else {
                snake_dir = (snake_dir + 1) % 4; // 오른쪽 회전
            }
            phase++;
        }

        time++; // 시간 증가

        // 다음 이동 좌표 계산
        int nx = snake[rear - 1][0] + dir_x[snake_dir];
        int ny = snake[rear - 1][1] + dir_y[snake_dir];

        // 맵 경계 체크
        if (nx < 0 || nx >= N || ny < 0 || ny >= N) {
            break; // 게임 종료
        }

        // 몸체 충돌 체크
        for (int i = front; i < rear; i++) {
            if (snake[i][0] == nx && snake[i][1] == ny) {
                return; // 게임 종료
            }
        }

        // 사과 여부 확인 및 이동 처리
        if (map[nx][ny] == 1) {
            map[nx][ny] = 0; // 사과 제거
            enqueue(nx, ny); // 뱀 길이 증가
        } else {
            enqueue(nx, ny); // 뱀 머리 이동
            dequeue();       // 뱀 꼬리 제거
        }

        // 디버깅용 출력
    }
}

int main() {
    // 입력 받기
    scanf("%d", &N);
    scanf("%d", &K);
    for (int i = 0; i < K; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        map[x - 1][y - 1] = 1; // 사과 위치 저장 (1-based -> 0-based)
    }
    scanf("%d", &L);
    for (int i = 0; i < L; i++) {
        scanf("%d %c", &action_time[i], &action_cmd[i]);
    }

    // 게임 실행
    game();

    // 결과 출력
    printf("%d\n", time);
    return 0;
}

 

코드 해설

 

1. 전역 변수 초기화

int N = 0; // 맵 크기
int K = 0; // 사과 개수
int L = 0; // 방향 전환 횟수
int map[100][100] = {0}; // 맵 정보
int action_time[100] = {0}; // 방향 전환 시간
char action_cmd[100] = {0}; // 방향 전환 명령
int dir_x[4] = {0, 1, 0, -1}; // 이동 방향: 오른쪽, 아래, 왼쪽, 위
int dir_y[4] = {1, 0, -1, 0};

• 맵 정보: map[100][100] 배열에 사과 위치를 저장합니다.
• 방향 정보:
  • dir_x, dir_y를 통해 오른쪽, 아래, 왼쪽, 위로 이동할 수 있도록 설정합니다.
  • 예를 들어, 오른쪽으로 이동할 경우 (x, y) → (x + dir_x[0], y + dir_y[0]).

---

2. 뱀 위치 저장을 위한 큐

int snake[10000][2];
int front = 0, rear = 0; // 큐의 앞과 뒤
int snake_dir = 0; // 초기 방향 (오른쪽)

• 뱀의 위치: snake 배열에 뱀의 머리와 꼬리 좌표를 저장합니다.
• 큐의 역할: 뱀의 길이를 동적으로 관리합니다.
  • enqueue: 머리를 큐에 추가.
  • dequeue: 꼬리를 큐에서 제거.

---

3. 뱀의 이동 로직

(1) 방향 전환 처리

if (phase < L && time == action_time[phase]) {
    if (action_cmd[phase] == 'L') {
        snake_dir = (snake_dir + 3) % 4; // 왼쪽 회전
    } else {
        snake_dir = (snake_dir + 1) % 4; // 오른쪽 회전
    }
    phase++;
}

• phase는 현재 방향 전환 명령의 단계를 나타냅니다.
• 시간과 현재 명령을 비교해 뱀의 방향을 업데이트합니다.
  • 'L'일 경우, 왼쪽으로 90도 회전 (+3 % 4).
  • 'D'일 경우, 오른쪽으로 90도 회전 (+1 % 4).

---

(2) 이동 좌표 계산

int nx = snake[rear - 1][0] + dir_x[snake_dir];
int ny = snake[rear - 1][1] + dir_y[snake_dir];

• 현재 머리 위치에 이동 방향을 더해 새로운 좌표 (nx, ny)를 계산합니다.

---

(3) 경계 및 충돌 체크

if (nx < 0 || nx >= N || ny < 0 || ny >= N) {
    break; // 맵 경계 초과
}
for (int i = front; i < rear; i++) {
    if (snake[i][0] == nx && snake[i][1] == ny) {
        return; // 자기 자신과 충돌
    }
}

• 새로운 좌표가 맵 경계를 넘거나, 뱀이 자기 몸과 충돌하면 게임을 종료합니다.

---

(4) 이동 처리

if (map[nx][ny] == 1) {
    map[nx][ny] = 0; // 사과 제거
    enqueue(nx, ny); // 뱀 길이 증가
} else {
    enqueue(nx, ny); // 머리 이동
    dequeue();       // 꼬리 제거
}

• 새로운 좌표에 사과가 있으면:
  • 사과를 제거하고 뱀의 길이를 증가시킵니다.
• 사과가 없으면:
  • 머리를 이동시키고 꼬리를 제거하여 길이를 유지합니다.

---

4. 결과 출력

printf("%d\n", time);

• 게임 종료 시점의 시간을 출력합니다.

---

실행 예제

입력

10
5
1 5
1 3
1 2
1 6
1 7
4
8 D
10 D
11 D
13 L

출력

14

실행 과정

1. 뱀은 (0, 0)에서 시작하여 오른쪽으로 이동.
2. 8초에 오른쪽(D)으로 방향 전환.
3. 사과를 먹으며 진행하다가 14초에 자기 몸과 충돌하여 종료.

---

개선 사항 및 팁

• 맵 초기화:
  • map 배열을 명시적으로 초기화하여 불필요한 값을 방지.
• 디버깅:
  • 이동마다 현재 뱀의 상태를 출력하여 과정을 시각화.

---

결론

이 코드는 큐를 활용하여 뱀의 길이를 동적으로 관리하며, 시뮬레이션 문제를 효율적으로 해결합니다. 방향 전환과 충돌 체크를 정확히 구현하는 것이 핵심입니다.

 

 

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.

 

 

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.