[프로그래머스] Lv2 - 전력망을 둘로 나누기 (파이썬)

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

코딩테스트 연습 - 전력망을 둘로 나누기

 

from collections import deque
import sys


def solution(n, wires):
    answer = sys.maxsize
    for i in range(len(wires)):
        new_wires = wires[:i] + wires[i+1:]
        arr = [[]for _ in range(n+1)]
        for x, y in new_wires:
            arr[x].append(y)
            arr[y].append(x)
        visited = [False for _ in range(n+1)]
        result = []
        for k in range(1, n+1):
            if not visited[k]:
                result.append(counting(n, arr, visited, k))
        answer = min(answer, abs(result[0] - result[1]))
    return answer if answer != sys.maxsize else -1


def counting(n, arr, visited, k):
    q = deque()
    q.append(k)
    visited[k] = True
    cnt = 1
    while q:
        x = q.popleft()
        for i in arr[x]:
            if not visited[i]:
                visited[i] = True
                q.append(i)
                cnt += 1
    return cnt

 

BFS
1. 전선들 중 각 전선을 뺀 나머지 전선을 new_wires로 정의
2. new_wires로 양방향 인접 리스트 정의 (arr), visited : 각 송전탑의 방문 여부
3. 송전탑을 완전 탐색
    - 해당 송전탑을 방문하지 않았으면 bfs (방문 여부를 체크하면서 개수 기록)
4. result값 차이 절댓값의 최솟값을 리턴

 

그래프 탐색을 BFS가 아니어도 여러 방법으로 풀 수 있다.

생각의 흐름대로 풀다 보니 조금 복잡한 방법으로 푼 것 같다.