20240321_전력망을 둘로 나누기(프로그래머스)

오늘의 TIL은 전력망을 둘로 나누기라는 프로그래머스의 문제에 대한 내용이다.

 

문제 링크

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

프로그래머스

 

 

문제 설명

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있는 경우에

이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 한다.

이 때, 두 전력망이 갖게되는 송전탑의 개수를 최대한 비슷하게 맞추려고 한다.

 

송전탑의 개수가 n, 전선 정보 wires가 매개변수로 주어진다.

전선들 중 하나를 끊어서 송전탑의 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때,

두 전력망이 가지고 있는 송전탑의 개수의 차이(절대값)를 return 하시오.

 

 

제한 조건

n은 2 이상 100 이하인 자연수이다.

wires는 길이가 n-1인 정수형 2차원 배열이다.

wries의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며,

이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미한다.

1 <= v1 < v2 <= n

전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않는다.

 

 

해결 방안

wires로 주어지는 2차원 배열을 가지고 그래프를 구성한다.

이 때, 그래프는 각 노드(송전탑)간의 연결 관계를 저장하기 위해

List<List<int>> 구조를 사용한다.

각 전선을 순서대로 제거하면서 제거한 전선으로 인해 분리된 두 부분의 전력망에서

각각의 송전탑 개수를 세어 차이를 계산한다(DFS 사용).

모든 전선을 위의 과정을 반복하며, 두 전력망 사이의 송전탑 개수 차이의 최소값을 구한다.

 

예시

n = 9

wires = [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]

인 문제의 전력망 트리 그림.

 

 

통과한 답안

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(int n, int[,] wires) {
        int answer = n;

        for (int i = 0; i < n - 1; i++)
        {
            List<List<int>> graph = new List<List<int>>();
            for (int j = 0; j <= n; j++)
            {
                graph.Add(new List<int>());
            }

            for (int j = 0; j < n - 1; j++)
            {
                if (i == j)
                {
                    continue;
                }
                int a = wires[j, 0];
                int b = wires[j, 1];
                graph[a].Add(b);
                graph[b].Add(a);
            }

            bool[] visited = new bool[n + 1];
            int count = DFS(1, graph, visited);

            answer = Math.Min(answer, Math.Abs(count - (n - count)));

        }
        return answer;
    }
    static int DFS(int node, List<List<int>> graph, bool[] visited)
    {
        visited[node] = true;
        int count = 1;

        foreach (var next in graph[node])
        {
            if (!visited[next])
            {
                count += DFS(next, graph, visited);
            }
        }

        return count;
    }
}

 

 

주어진 wires를 이용하여 그래프 구성하기

for (int i = 0; i < n - 1; i++)
{
    List<List<int>> graph = new List<List<int>>();
    for (int j = 0; j <= n; j++)
    {
        graph.Add(new List<int>());
    }

    for (int j = 0; j < n - 1; j++)
    {
        if (i == j)
        {
            continue;
        }
        int a = wires[j, 0];
        int b = wires[j, 1];
        graph[a].Add(b);
        graph[b].Add(a);
    }

 

그래프는 List<List<int>>의 형태로 작성한다.

이 때, graph.Add(new List<int>()); 의 방법으로 초기화하며

이후의 for문을 통해 전선들을 순회하며 그래프를 구성한다.

이 때, if문을 통해서 전선 하나를 제외한 그래프를 구성하므로,

각각의 전선을 제거한 그래프를 모두 그려볼 수 있다.

이 코드를 통해서 전력망에서 하나의 전선을 제외한 나머지로 구성된 그래프를 만들어,

해당 상태에서 두 부분으로 나뉜 전력망의 송전탑 개수를 계산할 수 있는 기반을 마련한다.

 

 

각 그래프에서 DFS를 이용하여 두 전력망 중 하나의 송전탑 개수를 계산하기

    bool[] visited = new bool[n + 1];
    int count = DFS(1, graph, visited);

    answer = Math.Min(answer, Math.Abs(count - (n - count)));

}

static int DFS(int node, List<List<int>> graph, bool[] visited)
{
    visited[node] = true;
    int count = 1;

    foreach (var next in graph[node])
    {
        if (!visited[next])
        {
            count += DFS(next, graph, visited);
        }
    }

    return count;
}

 

DFS에서 노드와 그래프, 방문했는지를 확인하는 bool을 이용하여

하나의 연결된 송전탑의 개수(count)를 계산한다.

이를 통해서 위의 for문에서 각각의 경우에 대해서 하나의 연결된 송전탑의 개수를 계산하고,

이를 초기 answer값(n)과 비교하여 더 적은 값을 answer에 저장하고,

이 과정을 모든 경우에 대해서 계산하면서 가장 작은 answer 값을 계산한다.

 

 

오늘은 완전탐색 카테고리를 갖고 있는 '전력망을 둘로 나누기'라는 문제를 풀어보았는데,

문제 자체는 간단해보이나 wires를 2차원 배열로 주어지는데,

이를 가지고 위의 이미지처럼 그림으로 이해하고,

이를 그래프로 구성하는 과정은 쉽지 않은 과정이었다.

특히, 완전탐색을 위해서 모든 경우의 수를 구하는 방식으로 문제를 해결하였는데

각각 하나의 전선을 제거할 때의 송전탑의 개수를 구하는 방식으로 최소값을 구하는 방식은

이 문제를 풀면서는 어떻게든 나온 결과지만,

다시 고민하여 문제를 푸는 경우에는 잘 생각나지 않을 것 같다.

 

위와 같은 이유로 조금은 난해하고 완벽히 이해하지 못한 문제였지만,

이렇게 정리하는 기회를 통해서,완전탐색, DFS, BFS의 문제를 좀 더 많이 풀어보면서

유사한 문제에 익숙해지는 연습을 해야될 것 같다.