[프로그래머스] 전력망을 둘로 나누기 (C++)
완전탐색 N개의 송전탑이 하나의 트리를 구성하며 연결되어 있는데, 간선 하나를 잘라서 두개의 트리로 분리할 때이 두개의 트리의 송전탑 개수 차가 최소가 되는 그 최소값을 반환하는 문제 두 송전탑을 잇는 간선이 이렇게 wires 라는 배열로 주어짐 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]간선은 한개씩만 주어지지만 양방향 간선임접근방법 완전탐색인 만큼..모든 간선을 잘라보면서 두 그래프의 노드 수 차이를 구해보면 된다.우선 인접행렬을 만들어서 사용했고,하나의 간선 (1,3) 을 자르면, 1로 시작해서 갈 수 있는 노드들을 모두 센다 큐를 하나 만들어서 bfs처럼 풀었음근데, 노드를 방문할 때 3이면 방문하지 않음 => 3으로부터 뻣어갈 수 있는 노드들은 방문하..
2024. 11. 4.