1. 활동 내역

• 알고리즘 문제 해결 전략 공부 및 문제풀이

1) 알고리즘 문제해결(bfs)

BFS는 그래프 탐색 알고리즘 중 하나로, bfs와 달리 "깊이 우선"으로 그래프를 탐색하는 방법이다.

• 동작 원리 및 구현 방법

bfs는 현재 정점에서 갈수 있는 인접한 정점을 모두 확인하고 기록한 이후에 기록한 정점들을 방문해 나가며 모든 인접 정점에 방문하거나 특정 목표에 다다르면 탐색을 종료한다. 이는 큐 자료구조에 방문한 인접 노드를 기록하여 구현할 수 있다.

해결할 문제: 뱀과 사다리 게임

#include <stdio.h>
#include <stdbool.h>
#define QUEUESIZE 10000

typedef struct {
    int front;
    int rear;
    int data[QUEUESIZE];
} Queue;

void init_queue(Queue *q) {
    q->front = q->rear = -1;
}

bool is_empty(Queue *q) {
    return q->front == q->rear;
}

void enqueue(Queue *q, int object) {
    q->data[++(q->rear)] = object;
}

int dequeue(Queue *q) {
    return q->data[++(q->front)];
}

int gameVisit[101];
int bam[101];
int sadari[101];
int result = 1000;

void bfs(int start) {
    Queue q;
    init_queue(&q);
    enqueue(&q, start);
    gameVisit[start] = 0;

    while (!is_empty(&q)) {
        int current = dequeue(&q);
        if (current == 100) {
            result = gameVisit[current];
            return;
        }

        for (int dice = 1; dice <= 6; dice++) {
            int next = current + dice;
            if (next > 100) continue;

            if (sadari[next] != 0) {
                next = sadari[next];
            } else if (bam[next] != 0) {
                next = bam[next];
            }

            if (gameVisit[next] == -1) {
                gameVisit[next] = gameVisit[current] + 1;
                enqueue(&q, next);
            }
        }
    }
}

int main(void) {
    int n, m;
    
    scanf("%d %d", &n, &m);
    
    for (int i = 0; i < 101; i++) {
        gameVisit[i] = -1;
        bam[i] = 0;
        sadari[i] = 0;
    }

    for (int i = 0; i < n; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        sadari[a] = b;
    }
    
    for (int i = 0; i < m; i++) {
        int c, d;
        scanf("%d %d", &c, &d);
        bam[c] = d;
    }
    
    bfs(1);
    printf("%d\\n", result);
    
    return 0;
}

이 문제에서는 주사위를 던져서 1번 칸에서 100번 칸까지 도달하는데 필요한 최소 횟수를 계산해야한다.

큐(Queue) 구조체와 초기화:

Queue 구조체는 BFS에서 사용할 큐를 구현한다. 큐의 front와 rear를 초기화하고, 데이터를 저장할 배열을 정의한다.

init_queue, is_empty, enqueue, dequeue 함수를 통해 큐의 기본 동작을 구현한다.

게임 상태 초기화:

gameVisit[101] 배열은 각 칸에 도달하기까지 필요한 주사위 던지기 횟수를 저장하며, 초기값은 -1로 설정해 아직 방문하지 않은 상태를 표시한다.

bam[101] 배열과 sadari[101] 배열은 각각 뱀과 사다리의 시작과 끝 지점을 기록한다.

BFS 함수:

bfs 함수는 1번 칸을 시작으로 BFS를 수행한다. 큐에 시작 칸을 넣고, 방문 처리를 한다.

현재 위치에서 주사위를 던져 1~6칸을 이동할 수 있다. 이동 후의 위치에 뱀이나 사다리가 있으면 해당 칸으로 이동한다.

아직 방문하지 않은 칸이라면, 그 칸을 방문 처리하고 큐에 추가한다. BFS는 이 과정을 반복해 100번 칸에 도달할 때까지 탐색한다.