프로그래머스 완전탐색 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 59분 소요

def check_edge(graph):

    from collections import deque

    # 시작 1
    queue = deque([1])
    visited = [0 for _ in range(len(graph)+1)]
    
    visited[1] = 1

    while queue:
        v = queue.popleft()

        for i in graph[v]:
            if not (visited[i]):
                queue.append(i)
                visited[i] = 1

    for idx,visit in enumerate(visited):
        if visit==0:
            visited[idx] = -1

    visited[0] = 0

    return sum(visited)

def solution(n, wires):
    import copy

    answer = len(wires)
    graph = {}

    for wire in wires:
        w1,w2 = map(int,wire)
        
        try:
            graph[w1].append(w2)
        except:
            graph[w1] = []
            graph[w1].append(w2)
        try:
            graph[w2].append(w1)
        except:
            graph[w2] = []
            graph[w2].append(w1)

    for wire in wires:

        graph2 = copy.deepcopy(graph)
        w1,w2 = map(int,wire)
        graph2[w1].remove(w2)
        graph2[w2].remove(w1)

        tmp = check_edge(graph2)

        if abs(tmp) < answer:
            answer = abs(tmp)

    return answer
    

트리(그래프) 구조로 이루어진 전력망을 최대한 비슷하게 둘로 나누는 문제입니다.

문제에서 트리구조라고 언급하였지만 손에 익은 양방향 그래프로 구현하였고
연결된 간선을 하나씩 끊어뜨리며 둘로 나뉜 전력망을 탐색하기 위해 bfs를 활용하였습니다. 이후 두 전력망 노드의 최소값을 도출하였습니다.

[다른사람의 풀이1]

# -*- coding: utf-8 -*-
import copy
def solution(n, wires):
    parent = [0] * (n+1)
    for i in range(1,n+1): #자기 부모는 자신으로 초기화
        parent[i] = i
    
    def find_parent(parent, x): #부모가 누구인지 찾기
        if parent[x] != x:
            return find_parent(parent, parent[x])
        return parent[x]
    
    def union_parent(parent, a, b):
        a = find_parent(parent, a) #a의 부모
        b = find_parent(parent, b) #b의 부모
        if a < b:
            parent[b] = a
        else:
            parent[a] = b
 
    res = n
    for i in range(len(wires)):
        parent_cp = copy.deepcopy(parent)
        for j in range(len(wires)): #하나씩 간선 끊어보기
            if i==j:
                continue
            a,b = wires[j]
            union_parent(parent_cp, a, b)
        
        for a,b in wires:
            parent_cp[a] = find_parent(parent_cp, a)    
            parent_cp[b] = find_parent(parent_cp, b)  
        res = min(abs(parent_cp.count(parent_cp[wires[i][0]]) - parent_cp.count(parent_cp[wires[i][1]])), res)
            
    return res

크루스칼 알고리즘의 union parent, find_parent 를 활용하여 해결한 풀이입니다. 이전에 크루스칼 알고리즘을 경험해보아 단번에 알아챌 수 있었습니다.

먼저 주어진 wires들을 하나씩 끊어가되 연결된 노드들의 부모값들을 찾아 대입합니다.

wires요소들 순서대로 순회했기때문에 순서에 따라 부모값들이 잘못 초기화 되어있을 경우가 있어

	for a,b in wires:
    	parent_cp[a] = find_parent(parent_cp, a)    
       	parent_cp[b] = find_parent(parent_cp, b)
        

으로 다시 초기화 해준 후 양 전력망의 최솟값을 구하는 방식입니다.

[다른 사람의 풀이2]

# -*- coding: utf-8 -*-
from collections import deque
def solution(n, wires):
    res = 0
    graph = [[] for _ in range(n+1)]
    for a,b in wires:
        graph[a].append(b)
        graph[b].append(a)
    
    def bfs(start):
        visited = [0] * (n+1)
        q = deque([start])
        visited[start] = 1
        cnt = 1
        while q:
            s = q.popleft()
            for i in graph[s]:
                if not visited[i]:
                    q.append(i)
                    visited[i] = 1
                    cnt += 1
        return cnt
            
    res = n
    for a,b in wires:
        #graph에서 remove
        graph[a].remove(b)
        graph[b].remove(a)
        
        res = min(abs(bfs(a) - bfs(b)), res)
        
        #다시 append
        graph[a].append(b)
        graph[b].append(a)
    
    return res

저의 풀이와 유사한 방식입니다. 이중 리스트를 통해 양방향 그래프를 구현하고
연결된 노드를 하나씩 제거하며 bfs 구조로 최솟값을 도출하는 문제입니다.

감사합니다.