전력망 둘로 나누기 파이썬 - jeonlyeogmang dullo nanugi paisseon

문제 설명

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

제한사항

• n은 2 이상 100 이하인 자연수입니다.
• wires는 길이가 n-1인 정수형 2차원 배열입니다.
  • wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
  • 1 ≤ v1 < v2 ≤ n 입니다.
  • 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.

입출력 예

입출력 예 설명

입출력 예 #1

• 다음 그림은 주어진 입력을 해결하는 방법 중 하나를 나타낸 것입니다.
• 
• 4번과 7번을 연결하는 전선을 끊으면 두 전력망은 각 6개와 3개의 송전탑을 가지며, 이보다 더 비슷한 개수로 전력망을 나눌 수 없습니다.
• 또 다른 방법으로는 3번과 4번을 연결하는 전선을 끊어도 최선의 정답을 도출할 수 있습니다.

입출력 예 #2

• 다음 그림은 주어진 입력을 해결하는 방법을 나타낸 것입니다.
• 
• 2번과 3번을 연결하는 전선을 끊으면 두 전력망이 모두 2개의 송전탑을 가지게 되며, 이 방법이 최선입니다.

입출력 예 #3

• 다음 그림은 주어진 입력을 해결하는 방법을 나타낸 것입니다.
• 
• 3번과 7번을 연결하는 전선을 끊으면 두 전력망이 각각 4개와 3개의 송전탑을 가지게 되며, 이 방법이 최선입니다.

• solution.c

💡solutions )

💬 전선이 연결돼 있는 형태를 나타내는 adj 인접행렬 만들기

💬 인접행렬을 for문으로 돌며 연결돼 있는 전선을 하나씩 끊어보기

💬인접행렬에서 remove() 메소드를 통해 해당 송전탑을 제거해준 후 연결 상태를 알아보기 위해 connect()함수 실행하기 -> 반환되는 visit 배열, 이때 연결돼 있는 송전탑은 visit배열에서 1로 나타나고, 나머지 송전탑은 0으로 나타내기 때문에 이들의 카운트 한 값의 차이의 최소값을 구하면 된다.

💬 전선 끊었던 것을 다시 연결해주어 다음 송전탑을 비교해야 한다. -> for문을 돌리고 있기 때문에 순서에 지장을 주지 않기 위해 adj[i] = [tmp] + adj[i] 으로 인접리스트 맨 앞쪽으로 확인한 송전탑(tmp)를 붙여줘야 하는 걸 주의해야 한다.

👨‍💻code )

def connect(lst, i, adj):
    stack = []
    for i in lst:
        stack.append(i)
    visit = [0]*len(adj)
    visit[i-1] = 1
    while stack:
        a = stack.pop()
        for i in adj[a-1]:
            if not visit[i-1]:
                stack.append(i)
                visit[i-1] = 1
    
    return visit

def solution(n, wires):
    adj = [[] for _ in range(n)]
    
    for a, b in wires:
        adj[a-1].append(b)
        adj[b-1].append(a)
    print(adj)
    min_v = 100
    for i in range(n):
        for j in range(len(adj[i])):
            tmp = adj[i][j]
            adj[i].remove(adj[i][j])
            if adj[i]:
                res = connect(adj[i], i, adj)
                min_v = min(min_v, abs(res.count(0) - res.count(1)))
            adj[i] = [tmp] + adj[i]
    return min_v

📌description )

코딩테스트 연습 - 9주차_전력망을 둘로 나누기

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

programmers.co.kr

문제 설명

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

제한사항

• n은 2 이상 100 이하인 자연수입니다.
• wires는 길이가 n-1인 정수형 2차원 배열입니다.
  • wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
  • 1 ≤ v1 < v2 ≤ n 입니다.
  • 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.

입출력 예

nwiresresult

입출력 예 설명

입출력 예 #1

• 다음 그림은 주어진 입력을 해결하는 방법 중 하나를 나타낸 것입니다.
• 
• 4번과 7번을 연결하는 전선을 끊으면 두 전력망은 각 6개와 3개의 송전탑을 가지며, 이보다 더 비슷한 개수로 전력망을 나눌 수 없습니다.
• 또 다른 방법으로는 3번과 4번을 연결하는 전선을 끊어도 최선의 정답을 도출할 수 있습니다.