<aside> 1️⃣

문제: 1326번 폴짝폴짝

개구리가 징검다리 사이를 뛰어다닐 때 징검다리에 쓰여 있는 수의 배수만큼 건너뛰어 갈 수 있음

N개의 징검다리 중 a에서b로 갈 때, 최소 몇 번 점프하여 갈 수 있는지 구하기

• a에서 b로 갈 수 없는 경우 -1 출력 </aside>

#include <stdio.h>
#include <stdlib.h>
#define MAX 10001

int N;
int arr[MAX];
int visited[MAX];

//큐 
typedef struct {
    int pos;
    int dist;
} Node;

Node queue[MAX*10];
int front = 0, rear = 0;

void enqueue(int pos, int dist) {
    queue[rear].pos = pos;
    queue[rear].dist = dist;
    rear++;
}

Node dequeue() {
    return queue[front++];
}

//BFS 함수
int BFS(int start, int end) {
    visited[start] = 1; //시작 위치
    enqueue(start, 0);

    while(front < rear) { ///큐가 빌 때까지 반복
        Node cur = dequeue();

        if(cur.pos == end) return cur.dist;

        int step = arr[cur.pos];
        //오른쪽 방향
        for(int k = 1; cur.pos + k*step <= N; k++) {
            int next = cur.pos + k*step;
            if(!visited[next]) {
                visited[next] = 1;
                enqueue(next, cur.dist + 1); //최소 점프 수
            }
        }
        //왼쪽 방향
        for(int k = 1; cur.pos - k*step >= 1; k++) {
            int next = cur.pos - k*step;
            if(!visited[next]) {
                visited[next] = 1;
                enqueue(next, cur.dist + 1);
            }
        }
    }
    return -1;
}

int main() {
    scanf("%d", &N);
    for(int i=1; i<=N; i++) scanf("%d", &arr[i]);

    int a, b;
    scanf("%d %d", &a, &b);

    int ans = BFS(a, b); 
    printf("%d\\n", ans);

    return 0;
}

<aside> 2️⃣

문제: 1347번 미로 만들기

미로에는 이동할 수 있는 방향 혹은 벽이 있음

이동할 수 있는 칸을 이동한 움직임이 주어졌을 때 미로 지도를 출력

• F는 앞으로 한칸
• LR은 칸 이동 없이 방향 전환
• 지도는 이동할 수 있는 칸을 . 벽을 #로 나타냄 </aside>

#include <stdio.h>

#define MAX 100

int main() {
    int n;
    char cmd[55];
    scanf("%d", &n);
    scanf("%s", cmd);

    //방향 인덱스 북동남서
    int dy[4] = {-1, 0, 1, 0};
    int dx[4] = {0, 1, 0, -1};
    int dir = 2; //시작은 남쪽

    //미로 전체를 벽으로
    char map[MAX][MAX];
    for (int i = 0; i < MAX; i++)
        for (int j = 0; j < MAX; j++)
            map[i][j] = '#';

    //시작 좌표는 가운데로
    int y = MAX/2, x = MAX/2;
    map[y][x] = '.';  //시작 위치 방문 처리

    //방문한 좌표 범위 추적
    int minY = y, maxY = y, minX = x, maxX = x;

    for (int i = 0; i < n; i++) {
        if (cmd[i] == 'L') {
            dir = (dir + 3) % 4; //왼쪽
        } else if (cmd[i] == 'R') {
            dir = (dir + 1) % 4; //오른쪽
        } else if (cmd[i] == 'F') {
            //현재 방향으로 한 칸 전진
            y += dy[dir];
            x += dx[dir];
            map[y][x] = '.'; //방문

            //방문 범위 갱신
            if (y < minY) minY = y;
            if (y > maxY) maxY = y;
            if (x < minX) minX = x;
            if (x > maxX) maxX = x;
        }
    }

    //실제 방문한 직사각형 범위만 출력
    for (int i = minY; i <= maxY; i++) {
        for (int j = minX; j <= maxX; j++) {
            printf("%c", map[i][j]);
        }
        printf("\\n");
    }

    return 0;
}