[알고리즘] 프로그래머스 Lv2 전력망 둘로 나누기

문제

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

풀이과정

n개의 송전탑이 트리 형태로 연결되어 있다 -> 인접 리스트로 정리해야겠다고 생각
연결선은 n-1개이고 n은 2~100 사이 숫자이다 -> 숫자가 크지 않다. 완전탐색으로 접근해볼만 하겠다.

1. wires를 순회하면서 인접리스트 생성
2. wires를 순회하면서 해당 wire를 끊는 경우에 대해서 BFS 방식으로 연결된 최대 송전탑 수를 구함
3. 차이의 최솟값을 기록

완전탐색 방식으로 접근하니 생각보다 금방 풀렸다.

코드

# 프로그래머스 전력망 둘로 나누기

# 트리 구조, 완전탐색

def solution(n, wires):
    def BFS(start, wire):
        queue = [start]
        visited = [False] * 101
        visited[start] = True

        while queue:
            now = queue.pop(0)
            for next in adj_list[now]:
                if [now, next] == wire or [next, now] == wire or visited[next]:
                    continue

                queue.append(next)
                visited[next] = True

        return sum(visited)

    adj_list = [[] for _ in range(n+1)]
    for wire in wires:
        # 양방향 연결
        adj_list[wire[0]].append(wire[1])
        adj_list[wire[1]].append(wire[0])

    diff = 100
    for wire in wires:
        A_len = BFS(wire[0], wire)
        B_len = BFS(wire[1], wire)
        # print(A_len, B_len)
        if abs(A_len - B_len) < diff:
            diff = abs(A_len - B_len)

    answer = diff
    return answer


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

n = 4
wires = [[1,2],[2,3],[3,4]]

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

print(solution(n, wires))