[SISS/C언어 스터디] 여름 6주차 스터디

여름 5주차 스터디

백준 제출 내역 화면 캡쳐

자율 2문제를 풀어서 제출하면 됩니다.

언어는 C언어만 가능합니다.

레벨 제한사항: Bronze 3 이상

 

2178

---

• 그래프 탐색 + bfs

// 2178.c

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

// bfs
void bfs(int **graph, int **visited, int n, int m)
{
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};

    // 동적 할당 (큐 / 최대 n*m)
    int size = n * m;
    int *queue_x = (int *)malloc(size * sizeof(int));
    int *queue_y = (int *)malloc(size * sizeof(int));
    int front = 0, rear = 0;

    // 시작(0, 0) 추가
    queue_x[rear] = 0;
    queue_y[rear] = 0;
    rear++;
    visited[0][0] = 1;

    while (front < rear)
    {
        int x = queue_x[front];
        int y = queue_y[front];
        front++;

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

            // 범위 외
            if (nx < 0 || nx >= n || ny < 0 || ny >= m)
            {
                continue;
            }

            // 미방문한 이동 가능 칸
            if (visited[nx][ny] == 0 && graph[nx][ny] == 1)
            {
                queue_x[rear] = nx;
                queue_y[rear] = ny;
                rear++;
                visited[nx][ny] = visited[x][y] + 1;
            }
        }
    }

    // 메모리 해제 (큐)
    free(queue_x);
    free(queue_y);
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);

    // graph, visited 메모리 할당
    int **graph = (int **)malloc(n * sizeof(int *));
    int **visited = (int **)malloc(n * sizeof(int *));

    for (int i = 0; i < n; i++)
    {
        graph[i] = (int *)malloc(m * sizeof(int));
        visited[i] = (int *)malloc(m * sizeof(int));
        memset(visited[i], 0, m * sizeof(int)); // visited 초기화 (0)

        for (int j = 0; j < m; j++)
        {
            scanf("%1d", &graph[i][j]); // 수 입력받기
        }
    }

    bfs(graph, visited, n, m);

    printf("%d\n", visited[n - 1][m - 1]);

    // 메모리 해제
    for (int i = 0; i < n; i++)
    {
        free(graph[i]);
        free(visited[i]);
    }
    
    free(graph);
    free(visited);

    return 0;
}

 

1197

---

• 최소 신장 트리 - 크루스칼

// 1197.c

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

// 부모를 찾음
int find_parent(int *parent, int x)
{
    if (parent[x] != x)
    {
        parent[x] = find_parent(parent, parent[x]);
    }
    return parent[x];
}

// 두 트리를 합침
void union_parent(int *parent, int a, int b)
{
    a = find_parent(parent, a);
    b = find_parent(parent, b);

    if (a < b)
    {
        parent[b] = a;
    }
    else
    {
        parent[a] = b;
    }
}

// 퀵소트 - 시간 초과 이슈로... (정렬 시 사용)
void quick_sort(int **edges, int left, int right)
{
    int i = left, j = right;
    int pivot = edges[(left + right) / 2][0];

    while (i <= j)
    {
        while (edges[i][0] < pivot)
            i++;
        while (edges[j][0] > pivot)
            j--;
        if (i <= j)
        {
            int *temp = edges[i];
            edges[i] = edges[j];
            edges[j] = temp;
            i++;
            j--;
        }
    }

    if (left < j)
        quick_sort(edges, left, j);
    if (i < right)
        quick_sort(edges, i, right);
}

int main()
{
    int v, e;

    // 입력
    scanf("%d %d", &v, &e);

    // 메모리 할당
    int *parent = (int *)malloc((v + 1) * sizeof(int));
    int **edges = (int **)malloc(e * sizeof(int *));
    
    for (int i = 0; i < e; i++)
    {
        edges[i] = (int *)malloc(3 * sizeof(int));
    }

    // 자기 자신을 부모로
    for (int i = 1; i <= v; i++)
    {
        parent[i] = i;
    }

    // 간선 입력
    for (int i = 0; i < e; i++)
    {
        scanf("%d %d %d", &edges[i][1], &edges[i][2], &edges[i][0]); // c, a, b 순으로 읽음
    }

    // 간선을 비용 순으로 정렬
    quick_sort(edges, 0, e - 1);

    int result = 0;

    // 크루스칼
    for (int i = 0; i < e; i++)
    {
        int cost = edges[i][0];
        int a = edges[i][1];
        int b = edges[i][2];

        // 사이클을 만들지 않으면 합침
        if (find_parent(parent, a) != find_parent(parent, b))
        {
            union_parent(parent, a, b);
            result += cost;
        }
    }

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

    // 메모리 해제
    free(parent);
    
    for (int i = 0; i < e; i++)
    {
        free(edges[i]);
    }
    
    free(edges);

    return 0;
}