프로그래머스86971 전력망 둘로 나누기

전력망 둘로 나누기 문제 설명은 다음 링크를 참고하면 됩니다. 문제 설명

프로그래머스

노드의 총합 n과 노드의 연결 정보를 가지고 있는 wires를 활용하여 두 그래프의 노드의 개수의 차이를 최대로 하는 결과를 반환하는 문제입니다.

 

하나의 그래프에서 임의의 노드 연결을 제거하였을 때 노드의 차이를 구하기 위해서는 모든 경우를 찾아보지 않고는 답을 확실하게 구할 수 없어 모든 경우의 수를 탐색하였습니다. 구현 방법은 다음과 같습니다. (그래프 연결 정보는 인접 리스트 표현법에 따라 저장한다)

1. 인접 리스트 표현법으로 그래프의 연결 정보를 저장한다.
2. wires 정보를 순환한다.
3. wires 정보의 vertex와 edge 정보를 1의 결과에서 제거한다.
4. bfs 탐색을 통해 vertex를 시작으로 그래프 개수를 구한다.
5. 개수의 차이를 최대로 하는 결과로 answer를 초기화한다.
6. 3의 결과를 원상복구 해주고, 2를 반복한다.

구현 방법을 코드로 구현하면 다음과 같습니다.

from collections import deque

def bfs(start, graph, visited):
    queue = deque()
    queue.append(start)
    visited[start] = True

    while queue:
        vertex = queue.popleft()

        for v in graph[vertex]:
            if not visited[v]:
                queue.append(v)
                visited[v] = True
    return visited.count(True)

def get_graph(n, wires):
    graph = [[] for _ in range(n + 1)]

    for vertex, edge in wires:
        graph[vertex].append(edge)
        graph[edge].append(vertex)
    return graph

def solution(n, wires):
    answer = n
    graph = get_graph(n, wires)

    for vertex, edge in wires:
        graph[vertex].remove(edge)
        graph[edge].remove(vertex)
        
        visited = [False for _ in range(n+1)]
        count = bfs(vertex, graph, visited)
        answer = min(answer, abs(n - count * 2))

        graph[vertex].append(edge)
        graph[edge].append(vertex)
    return answer

완전 탐색을 경우 모든 경우의 수를 탐색하는 것이기 때문에 효율적인 부분에서 항상 고민이 생깁니다.

 

해당 문제의 카테고리가 완전 탐색으로 분류되어 있어 별 고민 없이 완전 탐색을 사용하였지만 실제 코딩 테스트라고 생각한다면 완전 탐색을 풀이법으로 선택하는 것에는 "정답을 찾기 위해 모든 경우의 수를 탐색해야하는가?" 에 대한 물음에 답을 할 수 있을 때에만 사용하는 것이 좋다고 생각합니다.