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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

 

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

✅문제 https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이

jeongmin.tistory.com

  • 위 블로그를 참고했고 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