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

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/86971

코딩테스트 연습 - 9주차

 

약간 생각하느라 시간이 걸렸던 문제입니다.

처음에는 크루스칼 알고리즘으로 접근해야 하나? (풀었던 비슷한 문제) 하고 생각도 해 봤는데

각 전선에 별도의 가치가 존재하지 않고, 간선의 가치의 합이 아닌 노드의 개수의 차이를 최소화 하는 문제라서 이 방법으로는 실패했습니다.

 

그 다음으로 제가 시도한 방법은 전선을 하나씩 끊어 보며 dfs를 통해 탐색하는 방법입니다.

N은 최대 100이므로, 전선은 최대 99개가 존재합니다. 따라서 총 99번 동안, 각 전선을 한번씩 끊고 dfs를 돌려도 데이터의 수가 많지 않으므로 해결할 수 있습니다.

이 방법으로 성공적으로 풀었습니다.

 

각 dfs를 통해 방문한 노드들의 개수를 세면 되고, 노드는 중복해서 방문하지 않으므로 set을 활용하였습니다.

이번에 끊은 전선에 연결되어 있던 두 노드를 시작점으로 하고, dfs를 통해 두 개의 set에 각각 방문한 노드를 기록한 후,

set의 크기의 차의 절댓값을 계속 기록하였습니다.

끊었던 전선을 다시 잇는 것도 잊지 말아야 합니다.

 

채점 결과

이렇게 딱 풀릴 때는 기분이 너무 좋네요 ㅎㅎ