하나의 트리형태로 전부 이어진 송전탑이 주어졌을때 어느 한곳을 끊었을때 두 송전탑의 숫자가 최소한이 될수있도록 절대값을 구하면 되는문제이다. 사실 이 문제를 처음 봤을때는 리트코드에서 Union Find 형식으로 풀었던 Redundant Connection 문제가 생각이 났었다. 이 문제도 Union Find로 풀어볼까 생각했지만 문제가 요구하는 조건들을 계속 읽다보니 해당 알고리즘을 사용하기보다는 완전탐색 방법으로 접근하는게 가장 좋겠다 생각했다.
가장 처음으로는 wires안에있는 노드 들을 전부 열결 시켜줬다. Undirected Graph 이기때문에 양쪽으로 연결해주었고 와이어를 다시 읽으면서 끊어질 포인트와 끊어지게 될경우에 남는 송전탑의 숫자를 계산 해주었다. visited 벡터를 이용해서 두번째로 이어지는 포인트를 true 로 만들면서 절단했고 서로 따로 따로 dfs 를 해줘서 개수를 리턴하고 절대값으로 가장 작은 답을 계산했다.
간단한 dfs방식이고 각각 나뉘어진 노드들의 송전탑 개수를 구했다.
배운점:
1. 문제를 잘 읽어보자
2. dfs는 적절히 사용하자
성장하는 사람