목록전력망을 둘로 나누기 (1)

민규의 흔적

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

2024년 7월 5일문제 링크 : 프로그래머스 - 전력망을 둘로 나누기 문제 접근 위와 같이 모든 정점이 이어져 있는 한 트리가 주어질 때 간선 하나를 잘랐을 때 나눠진 두 트리의 정점의 개수 차이가 가장 적을 때의 해당 차이를 출력하는 문제이다. 처음 문제를 보고 단절선과 관련된 문제인가? 생각했지만, 모든 간선을 하나씩 제거해보았을 때 나눠진 두 트리의 정점 개수만큼 차를 완전탐색으로 구할 수 있는 문제라고 판단했다. ( 시간복잡도 계산은 맨 뒤 풀이 후기에서 후설하겠다 ) (단절선이란 ? : https://ymg5218.tistory.com/12) 주어진 간선 정보 중, 한 간선을 제거하였을 때 1번 정점을 시작으로 BFS 로직을 돌려 해당 정점과 이어진 정점들을 True로 치환하고, BFS 로직이..
프로그래머스 2024. 7. 5. 01:55
이전 Prev 1 Next 다음