[SISS/C언어 스터디] 25-1학기 7주차 스터디 - BFS/DFS, 추가 과제

[SISS/C언어 스터디] 25-1학기 7주차 스터디 - BFS/DFS, 추가 과제

: 7주차 (5/12~5/18) 프로그래머스 지정 1문제 (깊이/너비 우선탐색)- https://school.programmers.co.kr/learn/courses/30/lessons/87694

 

아이템 줍기

---

// 아이템 줍기.c

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 102  // (좌표 2배 확장) 50*2=100 이상
#define QUEUE_MAX 10000

int map[SIZE][SIZE];
bool visited[SIZE][SIZE];

// 상하좌우 이동
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

// BFS를 위한 큐
typedef struct {
    int x, y, dist;
} Node;

Node queue[QUEUE_MAX];
int front = 0, rear = 0;

void enqueue(int x, int y, int dist) {
    queue[rear++] = (Node){x, y, dist};
}

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

bool is_valid(int x, int y) {
    return x >= 0 && y >= 0 && x < SIZE && y < SIZE;
}

int solution(int **rectangle, size_t rectangle_row_len, size_t rectangle_col_len,
             int characterX, int characterY, int itemX, int itemY) {
    
    // 1. 좌표 확장 및 경계, 내부 그리기
    for (int i = 0; i < rectangle_row_len; i++) {
        int x1 = rectangle[i][0] * 2;
        int y1 = rectangle[i][1] * 2;
        int x2 = rectangle[i][2] * 2;
        int y2 = rectangle[i][3] * 2;

        // 사각형 내부 2로 채우기
        for (int x = x1 + 1; x < x2; x++) {
            for (int y = y1 + 1; y < y2; y++) {
                map[x][y] = 2;
            }
        }

        // 사각형 테두리 1로 채우기 (2는 덮지 않음)
        for (int x = x1; x <= x2; x++) {
            if (map[x][y1] != 2) map[x][y1] = 1;
            if (map[x][y2] != 2) map[x][y2] = 1;
        }
        for (int y = y1; y <= y2; y++) {
            if (map[x1][y] != 2) map[x1][y] = 1;
            if (map[x2][y] != 2) map[x2][y] = 1;
        }
    }

    // 2. BFS
    characterX *= 2;
    characterY *= 2;
    itemX *= 2;
    itemY *= 2;

    enqueue(characterX, characterY, 0);
    visited[characterX][characterY] = true;

    while (front < rear) {
        Node curr = dequeue();

        if (curr.x == itemX && curr.y == itemY) {
            return curr.dist / 2; // 2배로 확장했으므로 복원
        }

        for (int i = 0; i < 4; i++) {
            int nx = curr.x + dx[i];
            int ny = curr.y + dy[i];

            if (!is_valid(nx, ny)) continue;
            if (visited[nx][ny]) continue;
            if (map[nx][ny] != 1) continue;  // 테두리만 이동

            visited[nx][ny] = true;
            enqueue(nx, ny, curr.dist + 1);
        }
    }

    return 0;
}

아이템 줍기

 

1202

---

• 우선순위 큐

→ https://www.acmicpc.net/problem/1202

// 1202.c

#include <stdio.h>
#include <stdlib.h>

#define MAX 300001

// 보석(무게, 가격)
typedef struct {
    int weight;
    int price;
} Jewelry;

// 최대 힙
typedef struct {
    int data[MAX];
    int size;
} MaxHeap;

Jewelry jewelries[MAX]; // 보석 배열
int bags[MAX];          // 가방 용량 배열
MaxHeap pq;             // 최대 힙 (가격 기준)

// 최대 힙 삽입
void push(MaxHeap* h, int val) {
    int i = ++(h->size);
    while (i != 1 && h->data[i / 2] < val) {
        h->data[i] = h->data[i / 2];
        i /= 2;
    }
    h->data[i] = val;
}

// 최대 힙 삭제
int pop(MaxHeap* h) {
    if (h->size == 0) return 0;

    int max = h->data[1];
    int temp = h->data[(h->size)--];

    int parent = 1;
    int child = 2;
    while (child <= h->size) {
        if (child < h->size && h->data[child] < h->data[child + 1]) child++;
        if (temp >= h->data[child]) break;
        h->data[parent] = h->data[child];
        parent = child;
        child *= 2;
    }
    h->data[parent] = temp;
    return max;
}

// 보석 정렬용 비교 함수 (무게 기준)
int compare_jewelry(const void* a, const void* b) {
    Jewelry* j1 = (Jewelry*)a;
    Jewelry* j2 = (Jewelry*)b;
    return j1->weight - j2->weight;
}

// 가방 정렬용 비교 함수 (용량 기준)
int compare_int(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

long long solve(int N, int K) {
    qsort(jewelries, N, sizeof(Jewelry), compare_jewelry);
    qsort(bags, K, sizeof(int), compare_int);

    int idx = 0;
    long long sum = 0;

    for (int i = 0; i < K; i++) {
        // 가방에 담을 수 있는 모든 보석 가격 힙에 추가
        while (idx < N && jewelries[idx].weight <= bags[i]) {
            push(&pq, jewelries[idx].price);
            idx++;
        }

        // 가장 비싼 보석 선택
        if (pq.size > 0) {
            sum += pop(&pq);
        }
    }

    return sum;
}

int main() {
    int N, K;
    scanf("%d %d", &N, &K);

    // 보석 입력
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &jewelries[i].weight, &jewelries[i].price);
    }

    // 가방 입력
    for (int i = 0; i < K; i++) {
        scanf("%d", &bags[i]);
    }

    // 결과 출력
    printf("%lld\n", solve(N, K));
    return 0;
}

1202