[프로그래머스/C] 전력망을 둘로 나누기

 

https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

 

 

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

#define MAX 100

int adj[MAX + 1][MAX + 1];
int visited[MAX + 1];

int dfs(int v1, int n) {
    visited[v1] = 1;
    int cnt = 1;
    for (int i = 1; i <= n; i++) {
        if (adj[v1][i] && !visited[i])
            cnt += dfs(i, n);
    }
    return cnt;
}

int solution(int n, int** wires, size_t wires_rows, size_t wires_cols) {
    int answer = n;
    
    int v1, v2;
    memset(adj, 0, sizeof(adj));
    
    for (int i = 0; i < wires_rows; i++) {
        v1 = wires[i][0];
        v2 = wires[i][1];
        
        adj[v1][v2] = 1;
        adj[v2][v1] = 1;
    }

    // 하나씩 돌면셔 간선 끊고, 갯수 확인
    for (int i = 0; i < wires_rows; i++) {
        v1 = wires[i][0];
        v2 = wires[i][1];

        adj[v1][v2] = 0;	// 간선 끊기
        adj[v2][v1] = 0;

        memset(visited, 0, sizeof(visited)); // 방문배열 초기화

        int tmp = dfs(v1, n);			// v1 노드에 연결된 노드 갯수
        int dif = abs((n - tmp) - tmp); // 차이계산
        if (dif < answer) {
            answer = dif;
        }
        adj[v1][v2] = 1;	// 끊은 간선 되돌리기
        adj[v2][v1] = 1;
    }

    return answer;
}

 

1. 인접 행렬 초기화

    주어진 전선 정보에 대한 그래프를 인접 행렬 형태로 초기화 한다.

    adf[i][j] = 1 이면 노드 i 와 노드 j 가 연결된 것을 의미한다.

 

2. 간선 제거 및 탐색

    각 전선을 하나씩 제거 후 나눠진 서브 그래프 중 한쪽의 노드 수를 계산한다.

    

3. 최소 차이 계산

    두 서브 그래프의 노드 수의 차이를 통해 최소 차이를 찾는다. 

 

dfs 함수 구조

    현재 방문한 노드를 visited 에 기록한다.

    현재 노드에 연결된 노드들을 순회하여 현재 노드와 연결된 노드들 중 방문하지 않은 노드에 대해 dfs함수를 재귀적으로 호출한다.

    방문한 노드 수를 세서 리턴. 

 

 

참고) memset

#include <string.h>

void *memset(void *s, int c, size_t n);

메모리의 특정 영역을 원하는 값으로 채우는 데 사용

 

 

• s: 값을 설정할 메모리의 시작 주소.
• c: 메모리 영역을 채울 값. 이 값은 unsigned char로 변환되어 사용됨.
• n: 설정할 바이트의 수.