🍀 전력망 둘로 나누기

두 개의 전력망 네크워크를 나누었을 때 네트워크 내의 송전탑의 개수의 차의 최소값을 구하는 문제이다. 네트워크가 두 개로만 나눈다니 망정이지... 여러 개로 나누라고 했었으면 멘붕이 올 뻔했다...
네트워크 내의 송전탑의 개수를 셀 때 dfs를 이용하면 될 것 같았으며 송전탑을 방문했을 때 visited라는 배열은 연결된 전선을 자를 때마다 새로 초기화 해주어야 함을 느꼈다. 하지만, 어느 전선을 끊었을 때 송전탑 개수의 차가 최소가 될까??🤔를 고민하는 것에 시간을 많이 썼다. 아무리 생각해봐도 하나씩 다 끊어볼 수 밖에 없어 완전탐색으로 풀었다.

내가 문 로직의 수도 코드는 아래와 같다.

• 1️⃣ 송전탑 간 연결정보를 graph라는 이차원 배열로 만든다.
• 2️⃣ 전선을 끊고 붙일 수 있는 cut_wire 함수를 만든다.
• 3️⃣ for => wires(이어진 전선 정보)
  - 4️⃣ 전선 자르기
  - 5️⃣ for => 송전탑 개수만큼 돌면서 네트워크에 존재하는 송전탑 count(dfs)
  - 6️⃣ 전선 다시 붙이기

1️⃣ Python

# 1️⃣ 송전탑 간 연결정보를 graph라는 이차원 배열로 만든다.
def create_linked_wire(n, wires):
    linked_wire_info = [[False for _ in range(n)] for _ in range(n)]

    for start, end in wires:
        start = start - 1
        end = end - 1
        linked_wire_info[start][end] = linked_wire_info[end][start] = True

    return linked_wire_info

# 2️⃣ 전선을 끊고 붙일 수 있는 cut_wire 함수를 만든다.
def cut_wire(start, end, wires_info, cut=True):
    wires_info[start][end] = wires_info[end][start] = not cut


def solution(n, wires):
    answer = []
    linked_wire_info = create_linked_wire(n, wires) # 1️⃣
	
    # 5️⃣ 네트워크에 존재하는 송전탑의 개수를 dfs로 탐색
    def dfs(node_num, visited):
        count = 1

        for next_node, linked_or_not in enumerate(linked_wire_info[node_num]):
            if not visited[next_node] and linked_or_not == True:
                visited[next_node] = True
                count += dfs(next_node, visited)


        return count

	# 3️⃣ for => wires(이어진 전선 정보) 👉🏻 이어진 전선 정보를 돌면서 끊어서 네트워크 분류
    for cut_start, cut_end in wires:
        cut_start, cut_end = cut_start - 1, cut_end - 1
        visited = [False for _ in range(n)]
        node_counts = []
        
        # 4️⃣ 전선 자르기
        cut_wire(cut_start, cut_end, linked_wire_info, cut=True)
        
        # 5️⃣ for => 탐색 시작
        for node_num in range(n):
            if not visited[node_num]:
                visited[node_num] = True
                node_count = dfs(node_num, visited)
                node_counts.append(node_count)

        # 6️⃣ 전선을 잘랐으니 다른 전선을 잘라보기 위해서 다시 붙이기
        cut_wire(cut_start, cut_end, linked_wire_info, cut=False)
        answer.append(abs(node_counts[0] - node_counts[1]))

    return min(answer)

2️⃣ Javascript

function createGraph(n, wires){
    const graph = Array(n).fill(0).map(() => Array(n).fill(false));
    
    for (const [startNode, endNode] of wires){
        graph[startNode][endNode] = true;
        graph[endNode][startNode] = true;
    }
    
    return graph;
}

function cutNode(startNode, endNode, graph, cut=true){
    graph[startNode][endNode] = !cut;
    graph[endNode][startNode] = !cut;
}

function solution(n, wires) {
    const answer = [];
    const parsedWires = [...wires].map(([startNode, endNode]) => [startNode - 1, endNode - 1]); // 🛠️
    const graph = createGraph(n, parsedWires);
    
    function searchNetwork(node, visited){
        let count = 1;
        
        graph[node].forEach((connected, nextNode) => {
            if (!visited[nextNode] && connected){
                visited[nextNode] = true;
                count += searchNetwork(nextNode, visited);
            }
        })
        
        return count;
    }
    
    for (const [cutStartNode, cutEndNode] of parsedWires){
        const visited = Array(n).fill(false);
        const nodeCounts = [];
        cutNode(cutStartNode, cutEndNode, graph);
        
        for (let nodeNum = 0; nodeNum < n; nodeNum++){
            if (!visited[nodeNum]){
                visited[nodeNum] = true;
                nodeCount = searchNetwork(nodeNum, visited);
                nodeCounts.push(nodeCount)
            }
        }        
        
        cutNode(cutStartNode, cutEndNode, graph, cut=false);
        answer.push(Math.abs(nodeCounts[0] - nodeCounts[1]));
    }
    
    return Math.min(...answer);
}

아직 dfs와 같은 탐색이 익숙치 않아 연습할 겸 python으로 짜고 2틀 후에 javascript 코드로 다시 짜서 변수명이 조금 다르지만, 전체적인 로직은 같다. 그 전에 코드의 🛠️ 부분을 보면 python 코드와 같이 index가 송전탑의 위치이기 때문에 -1을 해주는 수고를 덜기 위해서 송전탑의 위치를 index로 맞춰주는 작업을 하여 parsedWires에 정보를 담았다.

🥺 다른사람풀이

def solution(n, wires):
    ans = n
    for sub in (wires[i+1:] + wires[:i] for i in range(len(wires))):
        s = set(sub[0])
        [s.update(v) for _ in sub for v in sub if set(v) & s]
        ans = min(ans, abs(2 * len(s) - n))
    return ans

일어나서 다른사람풀이 까서 블로깅하기

🔥 마치며