Skip to main content

86971 - 전력망을 둘로 나누기

info

풀이 키워드​

스포주의

완전탐색 bfs


풀이 코드​

info
  • 메모리: 9370 KB
  • 시간: 11 ms
from collections import deque

def solution(n, wires):
    # 양방향 그래프: idx번 송전탑에 대한 인접 송전탑
    graph = [[] for _ in range(n+1)]
    for w in wires:
        s, t = w
        graph[s].append(t)
        graph[t].append(s)
    
    # 간선 하나 끊어보고 2번 bfs 돌려서 그룹별 송전탑 개수 총합 구하기
    ans = 100
    for w in wires:
        s, t = w
        visited = [False for _ in range(n+1)] # 각 case마다 visited reset
        
        # bfs
        res = [] # 그룹별 송전탑 개수 총합
        for i in range(1, n+1):
            if visited[i]: continue
            
            q = deque()
            q.append(i)
            visited[i] = True

            cnt = 0
            while q:
                cur = q.popleft()
                cnt += 1
                for nxt in graph[cur]:
                    if set([cur, nxt]) != set([s, t]) and not visited[nxt]:
                        visited[nxt] = True
                        q.append(nxt)

            res.append(cnt)
        
        diff = abs(res[0] - res[1])
        ans = min(ans, diff)
                            
    return ans

풀이 해설​

예제 그림

전선을 하나 끊어서 송전탑들을 두 그룹으로 나누고, 각 그룹간 송전탑 수의 차이가 최소가 되도록 하는 문제이다.

전선은 n-1개인데 하나의 전선 끊어보는 경우마다 모든 송전탑을 세어보고 있으므로, 시간복잡도는 O(n2)O(n^2) 이다.


풀이는 다음의 순서로 풀었다.

  1. 양방향 그래프의 인접리스트 생성
  2. 전선을 끊고 bfs를 2번 돌려 각 그룹별 송전탑 수 카운팅
  3. 차이가 가장 적은 값을 최종 반환

여기서 2번의 경우, 전선을 끊기 위해 실제로 리스트 원소에 삭제 조작을 가한 것이 아니라

for nxt in graph[cur]:
    if set([cur, nxt]) != set([s, t]) and not visited[nxt]:
        visited[nxt] = True
        q.append(nxt)

상단과 같이, 끊을 전선의 양 쪽 vertex 값을 저장해두고 bfs 진행에서 막아버렸다.

그리고 양방향 그래프라 element-wise하게 비교하면 안돼서 set을 사용했다.


메모​

  • 코테 보기 전 아침에 워밍업으로 풀었는데 구현 버벅여서 풀이 시간 늘어짐
  • visited 처리는 항상 vertex 기준이라고 생각하자. (예외가 있는지 모르겠는데, 여태까지 본 적 없음.)