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

🔗

풀이

n이 최대 100이라 완전 탐색으로 풀어도 O(n^2) = 약 1만번의 연산이다.

모든 경로를 한 번씩 다 나눴다. 1-3 경로를 나눠보고 2-3 경로도 나눠보는 방식. 단 이미 나눠본 경로를 또 나눌 필욘 없으므로 1-3을 나눠봤다면 3-1이 나눠지지 않도록 했다.

탐색은 bfs와 dfs 두 가지 방식 모두 사용했는데 dfs가 좀 더 빨랐던 것 같다. 1-3을 자르게 되면 1에서부터 탐색을 시작하고 3과 연결된 부분을 제외하고 모두 탐색한다. 아래 그림에서보면 1에서 탐색을 시작하고 3과 연결된 부분은 탐색하지 않는다면 1밖에 없기 때문에 1을 반환하게 된다. 전체 전력망을 둘로 나눴을 때의 차이값을 구해야 하기 때문에 이 값(1)과 전체 전력망에서 이 값을 뺀 값(9-1)의 차이를 다시 구해야 한다.

dfs(깊이 우선 탐색) 방식

visited를 중복이 불가능한 set() 자료형으로 선언하고 함수의 인자 값으로 넘기면서 재귀로 구현.

def solution(n, wires):
    graph = defaultdict(list)

    for v1, v2 in wires:
        graph[v1].append(v2)
        graph[v2].append(v1)


    def dfs(s, e, visited):
        for x in graph[s]:
            if x != e and x not in visited:
                visited.add(x)
                visited = dfs(x, e, visited)
        return visited

    min_v = 1e9
    for i in sorted(graph):
        for j in graph[i]:
            if i > j:
                continue
            
            # print(dfs(i, j, {i}))
            min_v = min(min_v, abs(n - 2*len(dfs(i, j, {i}))))

    return min_v
    
from collections import defaultdict

bfs(너비 우선 탐색)구현

def solution(n, wires):
    graph = defaultdict(list)

    for v1, v2 in wires:
        graph[v1].append(v2)
        graph[v2].append(v1)


    def bfs(s, e):
        visited = [0]*(n+1)
        queue, cnt, visited[s] = [s], 1, 1
        while queue:
            x = queue.pop(0)

            for dx in graph[x]:
                if visited[dx] or dx == e:
                    continue

                visited[dx] = 1
                queue.append(dx)
                cnt += 1

        return cnt

    min_v = 1e9
    for i in sorted(graph):
        for j in graph[i]:
            if i > j:
                continue

            min_v = min(min_v, abs(n - 2*bfs(i, j)))

    return min_v
from collections import defaultdict