프로그래머스. 전력망을 둘로 나누기

tose33 2022. 1. 25. 22:16

코딩테스트 연습 - 전력망을 둘로 나누기

9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1

programmers.co.kr

다음과 같은 2차원 벡터에 각 노드별로 이동할수 있는 노드를 푸쉬해 관계를 형성한다.

vector<vector<int> edges(110, vector<int>(0))

주어진 wires 배열을 순회하면서 관계를 하나씩 끊어본다.

관계를 끊는다는 것은 하나의 노드에서 dfs로 탐색할때 관계가 끊긴 노드는 이동하지 않도록 하는 것이다.

예를들어 wires[0] = {1,3}일때면 1과 3의 관계를 끊어보고,

1에서부터 dfs를 돌아보고, 3에서부터도 돌아봐서 각각 방문할수 있는 노드의 수의 차를 구하면 된다.