프로그래머스 - 9주차 위클리 챌린지- 전력망을 둘로 나누기

프로그래머스 - 9주차 위클리 챌린지- 전력망을 둘로 나누기

[문제 바로가기]

1. 유형

트리, union-find

2. 풀이

2-1. 해설

이 문제는 네이버 공채 기출문제라고 합니다.

처음 접근법은 2가지 묶음으로 나눠야 합니다. 그러기 위해서 저는 Union-find를 사용했습니다.

시뮬레이션을 돌려봅시다. 예제1번에서 처럼 4-7간선을 지워봅시다.

그리고 union-find를 돌리면, 아래 그림처럼 배열이 초기화 될거에요. 그럼 1의 개수와 7의 개수의 차이를 구하면 끝!

3. 코드

import java.util.*; class Solution { static int p[], MIN=987654321; public int solution(int n, int[][] wires) { int answer = -1; for(int i=0; i

from http://moons-memo.tistory.com/257 by ccl(A) rewrite - 2021-10-06 15:01:17