[python][프로그래머스] 전력망을 둘로 나누기 (BFS 문제)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

 

 

• 레벨 2
• 어떻게 풀어야할지 감도 안잡혀서 고민하다가 풀이를 찾아봤다
• https://jeongmin.tistory.com/5

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

• 위 블로그를 참고했고 30분은 커녕 몇시간은 앉아있어야 생각이 날만한 (내 입장에서는) 기발한 풀이였다..
• 일단 각자 노드에 연결 되어있는 노드들을 이중 리스트에 담아주고 각자 노드들과 이어진 노드의 개수를 bfs로 찾은 다음, v1과 v2의 사이를 끊는다면 노드의 개수가 몇개가 차이가날지 계산하는 방식이다
• 연결을 끊었을 때 노드 개수 차이는 v1과 v2를 서로의 리스트에서 없애준 다음 bfs를 돌려 이어진 노드 개수를 찾은 다음 abs(bfs(v1) - bfs(v2))로 그 차이를 찾을 수 있다

from collections import deque

def solution(n, wires):
    def bfs(x):
        queue = deque([x]) # 리스트 형식으로 넣어줘야 밑에 for loop에서 돌릴 수 있음
        visited = [0] * (n + 1) # 방문 여부 확인
        visited[x] = 1
        count = 1
        while queue: # 큐가 빌때까지
            curr = queue.popleft()

            for i in graph[curr]: # curr 노드랑 이어진 노드들을 돌면서 확인
                if not visited[i]: # 방문한적 없다면
                    visited[i] = 1 # 방문처리
                    queue.append(i) # 큐에 넣어주기
                    count += 1 # 카운트 올리기
        return count # 카운트 반환
    
    graph = [[] for _ in range(n+1)] 
    
    for v1, v2 in wires: # graph리스트의 index = 현재 노드, nested 리스트 안에 이어진 노드들 저장
        graph[v1].append(v2)
        graph[v2].append(v1)

    res = n # minimum을 찾아야되기 때문에
    for v1, v2 in wires: # 완전 탐색 부분
        graph[v1].remove(v2) # 연결 끊기
        graph[v2].remove(v1)

        res = min(abs(bfs(v1) - bfs(v2)), res)

        graph[v1].append(v2) # 다시 이어주기
        graph[v2].append(v1)
    
    return res