[프로그래머스] Lv 2. 전력망을 둘로 나누기

완전탐색으로 분류된 문제이며, 트리라는 구조를 생각하게 하게 하는 문제였다.

항상 완전탐색 문제를 풀기전에는 이 모든 경우를 전부 연산하면 제한시간에 걸리는게 아닌가? 라는 생각이 든다.

최악의 경우를 생각해서 runtime을 예상하면 된다고 한다. (10억번 연산에 1초)

해당 문제는 정해진 runtime이 없지만 10초라고 생각하고 계산해보자. (메모리 제약은 100MB로 넉넉하게 주는게 아니면, 어쩌면 DP문제라고 바로 알아차릴 수 있을지도?,,)

노드수는 최대 100개 그렇다면 만들어질 수 있는 edge수는 n(n+1)/2 = 약 5000개

스펙: map=100*100, visitied=100, edge수 5000개

완전탐색의 경우, [map 생성 및 접근:20,000, visitied 생성 및 탐색: 200 ] 이 과정을 5000번 수행

결과 --> 20,000*5,000=100,000,000번

대략 0.1sec 으로 충분하다고 판단할 수 있겠다.

def solution(n, wires):

    def bfs(map, start, visited):
        queue = []
        queue.append(start)
        visited[start] = True
        cnt = 0
        while queue:
            v = queue.pop()
            cnt += 1
            for i in map[v]:
                if not visited[i]:
                    queue.append(i)
                    visited[i] = True
        return cnt
    min = n - 2
    for i in range(len(wires)):
        temps = wires.copy()
        map = [[] for _ in range(n+1)]
        visited = [False] * (n+1)
        temps.pop(i)
        for wire in temps:
            x, y = wire
            map[x].append(y)
            map[y].append(x)
        for idx, g in enumerate(map):
            if g != []:
                start = idx
                break
        cnts = bfs(map, start, visited)
        other_cnts = n - cnts
        if abs(cnts - other_cnts) < min:
            min = abs(cnts-other_cnts)

    
    return min