99클럽 코테 스터디 10일차 TIL - 86971 전력망을 둘로 나누기

86971. 전력망을 둘로 나누기 / c++ / level2 / 18분

문제 및 코드

접근 방식

완전 탐색

1. 노드가 100개이므로 인접행렬을 만들어도 100 * 100 개, 메모리 크기는 40KB(정수의 경우)가 되므로 충분했다.
2. wires를 돌면서 두 노드를 모두 연결해줬다. (양방향 그래프)
3. 다시 wires를 돌면서, 이번엔 두 노드를 모두 끊어준 뒤, 각 노드를 시작점으로 하여 DFS를 계산해줬다.
4. 그렇게 나온 두 수 (두 전력망이 가지고 있는 송전탑의 개수)를 뺀 값의 절대값을 미리 최대값 (101)개를 취한 answer와 비교하여 더 작다면 answer를 갱신해줬다.
5. answer를 반환

생각해 볼 점

1. DFS를 맨 처음 시작할 때, 나눠진 두 노드의 방문 처리를 안해줬더니 테스트 케이스 1번이 틀렸었다. 사소해서 놓치기 쉬운 부분이므로 다음부터는 꼭 집고 넘어가야겠다.
2. 인접행렬에 비용이 들어가는게 아니라 연결 되어있는지 여부가 들어가므로 bool로 선언했다면 메모리를 아낄 수 있었다.

해시태그

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL