[Programmers] 전력망 둘로 나누기

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

 

Note

자료구조, 알고리즘의 개념에 대해 다시 생각해보게 해주는 문제였다. 쉬운 문제만 풀었을 때는 문제를 잘 이해하고 구현하는 과정에만 집중하면 된다고 생각했다. 하지만 역시 기본개념이 중요하다. 이 문제를 풀면서 트리, 트리 탐색에 대해서 다시 복습하는 기회가 되었다. 

개념이 부족할 때는 무작정 완전탐색으로만 문제를 해결하려고 하는 경향이 많았다. 이 문제에서도 처음에는 완전탐색으로 문제를 해결했다. 답은 나오지만 좋은 방법은 아니다. 자료구조, 알고리즘의 개념이 더 정확하게 쌓여있었다면 더 효율적인 코드를 작성할 수 있다.

 

 

wires의 최대값이 100이기 때문에 송전탑 연결상태를 하나씩 모두 끊어보면서 답을 구했다. 반복문을 통해 연결상태를 제거하고, 제거된 상태에서 한쪽 방향의 송전탑 개수(cnt)를 구한다. 그리고 반대편의 개수는 n-cnt를 통해 둘의 차이값을 계산하고, 최소값을 구하면 된다.

 

 

 

Code

from collections import deque

def solution(n, wires):
    answer = 101
    graph = [[] for k in range(n+1)]
    #make graph
    for wire in wires:
        graph[wire[0]].append(wire[1])
        graph[wire[1]].append(wire[0])

    for wire in wires:
        graph[wire[0]].remove(wire[1])
        graph[wire[1]].remove(wire[0])
        checked = [False]* (n+1)

        cnt = 1

        #BFS
        q = deque()
        q.append(wire[0])
        checked[wire[0]] = True

        while q:
            cur_node = q.popleft()

            for next_node in graph[cur_node]:
                if not checked[next_node]:
                    checked[next_node] = True
                    q.append(next_node)
                    cnt += 1

        dif = abs((n - cnt) - cnt)

        if dif < answer:
            answer = dif

        graph[wire[0]].append(wire[1])
        graph[wire[1]].append(wire[0])

    return answer

from collections import deque

def solution(n, wires):
    answer = 101
    graph = [set() for k in range(n+1)]
    checked = [False]* (n+1)
    #make graph
    for wire in wires:
        graph[wire[0]].add(wire[1])
        graph[wire[1]].add(wire[0])

    for wire in wires:
        graph[wire[0]].remove(wire[1])
        graph[wire[1]].remove(wire[0])
        checked = [False]* (n+1)

        cnt = 1

        #BFS
        q = deque()
        q.append(wire[0])
        checked[wire[0]] = True

        while q:
            cur_node = q.popleft()

            for next_node in graph[cur_node]:
                if not checked[next_node]:
                    checked[next_node] = True
                    q.append(next_node)
                    cnt += 1

        dif = abs((n - cnt) - cnt)

        if dif < answer:
            answer = dif

        graph[wire[0]].add(wire[1])
        graph[wire[1]].add(wire[0])

    return answer

from collections import deque

def solution(n, wires):
    answer = 101
    graph = [[] for _ in range(n+1)]
    #make graph
    for wire in wires:
        graph[wire[0]].append(wire[1])
        graph[wire[1]].append(wire[0])

    for wire in wires:
        checked = [False]*(n+1) 
        cnt = 1

        #BFS
        q = deque()
        q.append(wire[0])
        checked[wire[0]] = True
        checked[wire[1]] = True

        while q:
            cur_node = q.popleft()

            for next_node in graph[cur_node]:
                if not checked[next_node]:
                    checked[next_node] = True
                    q.append(next_node)
                    cnt += 1

        dif = abs((n - cnt) - cnt)

        if dif < answer:
            answer = dif

    return answer

첫 번째 코드는 송전탑 제거 과정을 인접리스트 방식으로 연결한 트리에서 list.remove를 통해 직접 연결상태를 제거해 주었는데, list에서 중간의 값을 제거하면 뒤에 데이터를 연속적으로 배열하기 위해 모두 당겨와야 하므로 연산낭비가 발생하였고, 이를 개선하기 위해 제거 상태를 방문처리를 통해 BFS가 탐색하지 못하도록 제거상태를 표시해 주 었다.

그리고 또 다른 방법으로 2차원 배열의 각 원소의 값을 list가 아닌 set으로 하여 remove 의 시간복잡도를 O(1)로 줄였다. list의 remove 시간복잡도는 최대 O(N)이지만 set은 O(1)이기때문이다.

문제풀이 실수
연결망을 제거할 때마다 새로 트리를 탐색해야하기때문에 트리 방문 여부를 매번 초기화 해주어야 하는데 BFS 방문전 최초 checked 배열을 초기화하고 반복문에서 BFS탐색 마다 방문 여부 초기화를 해주지 않아 버그를 잡지 못하는 실수를 했다.