[Python 파이썬] 프로그래머스 - 전력망을 둘로 나누기

2024년 7월 5일

문제 링크 : 프로그래머스 - 전력망을 둘로 나누기

---

문제 접근

 

 
위와 같이 모든 정점이 이어져 있는 한 트리가 주어질 때 간선 하나를 잘랐을 때 나눠진 두 트리의 정점의 개수 차이가 가장 적을 때의 해당 차이를 출력하는 문제이다.
 
처음 문제를 보고 단절선과 관련된 문제인가? 생각했지만, 모든 간선을 하나씩 제거해보았을 때 나눠진 두 트리의 정점 개수만큼 차를 완전탐색으로 구할 수 있는 문제라고 판단했다. ( 시간복잡도 계산은 맨 뒤 풀이 후기에서 후설하겠다 )
 
(단절선이란 ? : https://ymg5218.tistory.com/12)
 
주어진 간선 정보 중, 한 간선을 제거하였을 때 1번 정점을 시작으로 BFS 로직을 돌려 해당 정점과 이어진 정점들을 True로 치환하고, BFS 로직이 끝났을 때 True인 정점의 개수와 False인 정점의 개수 차이를 구해 가장 차이가 적은 값을 출력하면 되도록 로직을 구성하고자 하였다.

---

전체 코드

 

from collections import deque

def bfs(remove, n, wires):
    queue = deque()
    visited = [False] * (n + 1)

    graph = [[] for _ in range(n + 1)]
    for i in range(len(wires)):
        # 간선 하나 제외
        if i == remove:
            continue
        v1 = wires[i][0]
        v2 = wires[i][1]
        graph[v1].append(v2)
        graph[v2].append(v1)

    # 1을 시작점으로 bfs 시작
    # 1을 시작으로 연결된 트리와, 연결되지 못한 트리 두 그룹의 개수 차이를 return
    queue.append(1)
    visited[1] = True

    while queue:
        now_v = queue.popleft()
        for next_v in graph[now_v]:
            if not visited[next_v]:
                visited[next_v] = True
                queue.append(next_v)
    tree_1 = 0
    tree_2 = 0

    for i in range(1, n + 1):
        if visited[i]:
            tree_1 += 1
        else:
            tree_2 += 1

    return abs(tree_1 - tree_2)

def solution(n, wires):
    answer = n + 1

    for i in range(len(wires)):
        answer = min(answer, bfs(i, n, wires))

    return answer

if __name__ == "__main__":
    print(solution(9, [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]))

---

풀이 후기

 
시간초과를 우려했지만, 생각해보니 인접리스트 형태의 그래프에서 BFS 알고리즘을 적용시켰을 때 O(V + E)의 시간복잡도를 가지고, 모든 간선의 개수만큼 BFS를 수행하니 O(E * (V + E))의 시간복잡도를 보이게 될 것이다.
사이클이 존재하지 않는 무방향 그래프에서 간선의 최대 개수는 V - 1으로, O((V - 1) * (V + V - 1)) ~= O(V^2)의 시간복잡도를 가진다.
V의 최대값은 100이므로 시간적으로 충분히 여유로울 수 있는 코드였다고 생각한다.