[SISS/C언어 스터디] 25-1학기 4주차 스터디 - 완전 탐색, 추가 과제

[SISS/C언어 스터디] 25-1학기 4주차 스터디 - 완전 탐색, 추가 과제

: 4주차 (3/31~4/6) 프로그래머스 지정 1문제 (완전탐색)- https://school.programmers.co.kr/learn/courses/30/lessons/86971

 

전력망을 둘로 나누기

---

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

#define MAX_N 100

// 인접 리스트를 사용한 그래프 표현
int graph[MAX_N + 1][MAX_N + 1];
int visited[MAX_N + 1];

// DFS를 이용하여 연결된 송전탑 개수 계산
int dfs(int node, int n) {
    visited[node] = 1;
    int count = 1;
    
    for (int i = 1; i <= n; i++) {
        if (graph[node][i] == 1 && !visited[i]) {
            count += dfs(i, n);
        }
    }
    
    return count;
}

int solution(int n, int** wires, size_t wires_rows, size_t wires_cols) {
    int min_diff = n;
    
    // 그래프 초기화
    memset(graph, 0, sizeof(graph));
    
    // 그래프 생성
    for (size_t i = 0; i < wires_rows; i++) {
        int v1 = wires[i][0];
        int v2 = wires[i][1];
        graph[v1][v2] = 1;
        graph[v2][v1] = 1;
    }
    
    // 모든 간선을 하나씩 끊어보며 최소 차이 계산
    for (size_t i = 0; i < wires_rows; i++) {
        int v1 = wires[i][0];
        int v2 = wires[i][1];
        
        // 전선 끊기
        graph[v1][v2] = 0;
        graph[v2][v1] = 0;
        
        // 방문 배열 초기화
        memset(visited, 0, sizeof(visited));
        
        // 한쪽 네트워크의 송전탑 개수 구하기
        int count = dfs(v1, n);
        
        // 두 네트워크 간의 차이 계산
        int diff = abs((n - count) - count);
        if (diff < min_diff) {
            min_diff = diff;
        }
        
        // 전선 복구
        graph[v1][v2] = 1;
        graph[v2][v1] = 1;
    }
    
    return min_diff;
}

전력망을 둘로 나누기

 

2110

---

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

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

// 오름차순 - qsort()
int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    int N, C;
    scanf("%d %d", &N, &C); // 집 개수(N)와 공유기 개수(C)
    
    int arr[N];
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]); // 집 좌표
    }
    
    qsort(arr, N, sizeof(int), compare); // 집 좌표 정렬
    
    int start = 1; // 최소 거리
    int end = arr[N-1] - arr[0]; // 최대 거리
    int result = 0;
    
    // 이진 탐색
    while (start <= end) {
        int mid = (start + end) / 2; // 공유기 간의 거리 후보
        int current = arr[0]; // 첫 번째 공유기를 첫 번째 집에
        int count = 1; // 공유기 개수
        
        // 공유기 설치 가능 여부 확인
        for (int i = 1; i < N; i++) {
            if (arr[i] >= current + mid) { // 현위치에서 mid 거리 이상일 경우 설치
                count++;
                current = arr[i];
            }
        }
        
        // 공유기 설치 수가 목표보다 이상일 경우 거리 늘림
        if (count >= C) {
            result = mid;
            start = mid + 1;
        } else { // 공유기 설치 수가 목표보다 미만일 경우 거리 줄임
            end = mid - 1;
        }
    }
    
    printf("%d\n", result);
    return 0;
}

2110