[99클럽/코딩테스트 챌린지/C++] 전력망을 둘로 나누기 문제 해결

문제 링크:

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

프로그래머스

문제 요약

이 문제는 주어진 송전탑과 전선 정보에서, 전선 하나를 끊어 두 전력망으로 나누었을 때 송전탑 개수의 차이가 최소가 되도록 하는 것입니다.

문제의 주요 조건:

1. 입력으로 주어진 송전탑 네트워크는 항상 트리 구조입니다.
2. 전선 하나를 끊으면 두 전력망으로 분리됩니다.
3. 송전탑의 개수를 비교해 그 차이를 최소화해야 합니다.

문제 해결 접근법

1. 그래프를 인접 리스트로 표현

• 전선으로 연결된 송전탑 관계를 그래프의 형태로 나타냅니다.
• 인접 리스트를 사용하여 각 송전탑에 연결된 다른 송전탑의 정보를 저장합니다.

2. 전선 하나를 끊고 네트워크를 분리

• 모든 전선을 한 번씩 끊고, 두 네트워크의 송전탑 개수를 계산합니다.
• 전선을 끊는 것은 인접 리스트에서 해당 연결을 제거하는 것으로 구현됩니다.

3. BFS를 이용한 송전탑 개수 계산

• 분리된 네트워크에서 하나의 송전탑을 시작으로 BFS를 사용해 연결된 송전탑의 개수를 계산합니다.
• 전체 송전탑 개수에서 BFS로 계산된 송전탑 개수를 빼면 다른 네트워크의 송전탑 개수를 구할 수 있습니다.

4. 송전탑 개수 차이의 최소값 찾기

• 각 전선을 끊었을 때 두 네트워크의 송전탑 개수 차이를 계산하여 최소값을 갱신합니다.

코드 설명

#include <iostream>
#include <vector>
#include <math.h>
#include <queue>
#include <algorithm>
using namespace std;

vector<int> visited;
vector<vector<int>> graph;

// BFS를 이용해 네트워크의 송전탑 개수를 계산
int bfs(int start) {
    int count = 0;
    queue<int> q;
    q.push(start);
    visited[start] = 1;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        count++;
        for (int nei : graph[cur]) {
            if (visited[nei]) continue;
            q.push(nei);
            visited[nei] = 1;
        }
    }
    return count;
}

// 주어진 문제 해결
int solution(int n, vector<vector<int>> wires) {
    int answer = n;
    graph = vector<vector<int>>(n + 1);

    // 그래프 생성 (인접 리스트)
    for (const auto& wire : wires) {
        int from = wire[0];
        int to = wire[1];
        graph[from].push_back(to);
        graph[to].push_back(from);
    }

    // 각 전선을 끊고 네트워크를 분리
    for (const auto& wire : wires) {
        visited = vector<int>(n + 1);

        // 전선을 끊는다
        int from = wire[0];
        int to = wire[1];
        graph[from].erase(remove(graph[from].begin(), graph[from].end(), to), graph[from].end());
        graph[to].erase(remove(graph[to].begin(), graph[to].end(), from), graph[to].end());

        // BFS를 통해 송전탑 개수를 계산
        int a = bfs(from);
        int b = n - a;

        // 두 네트워크 송전탑 개수 차이의 최소값 갱신
        answer = min(answer, abs(a - b));

        // 전선을 복구한다 (Backtracking)
        graph[from].push_back(to);
        graph[to].push_back(from);
    }

    return answer;
}

 

배운 점

1, 인접 리스트를 활용한 그래프 구현

• 처음에는 전력망 네트워크를 처리하기 위해 인접 리스트를 사용하는 것을 떠올리지 못했습니다.
• 트리 구조와 그래프의 관계를 이해하고, 인접 리스트를 활용해 그래프를 구현하는 방법을 배웠습니다.

2, BFS를 활용한 연결된 노드 탐색

• BFS를 사용해 연결된 송전탑 개수를 계산하는 방법을 익혔습니다.
• queue를 활용하여 탐색의 효율성을 높이고, 방문 여부를 관리하기 위해 visited 배열을 사용했습니다.

3, 그래프 복구(Backtracking)

• 전선을 끊은 후 탐색이 끝나면 원래 상태로 복구하는 작업(Backtracking)이 필요했습니다.
• erase와 push_back을 통해 그래프의 상태를 원래대로 되돌리는 방법을 학습했습니다.

4, 최소값 갱신 로직

• 문제의 조건에 맞는 최소값을 갱신하기 위해 min 함수와 절대값 계산을 활용했습니다.
• 모든 경우를 탐색하고 최적의 결과를 도출하는 완전 탐색의 중요성을 다시 확인했습니다.

결론

이 문제를 통해 트리 구조의 그래프 문제를 해결하는 방법을 학습할 수 있었습니다. 특히, 인접 리스트를 사용해 그래프를 표현하는 방법과 BFS를 활용한 노드 탐색이 매우 유용한 도구임을 깨달았습니다. 앞으로도 유사한 그래프 문제에서 이 접근 방식을 활용할 수 있을 것입니다. 😊