[백준 2606번] 바이러스

난이도: 실버 III

문제 링크: https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

지금까지 다른 문제를 풀 때는 먼저 머릿속으로 생각을 하고, C++로 구현해서 정답 판정을 받은 후에, 같은 알고리즘을 Java 문법으로 다시 작성하는 식으로 접근하였습니다.

하지만 이런 식으로는 문제 하나를 푸는데 너무 오래 걸려서, 이번에 처음으로 순수 Java로 문제를 풀어 보았습니다.

 

문제를 단순화해서 생각해 보면,

1부터 n까지의 노드가 있고, 노드 간의 연결 정보가 주어집니다. Union-find 자료구조를 사용해서 각 노드 사이의 부모를설정해 주면 되는데, 낮은 노드일수록 우선순위를 줍니다.

이후 1번 노드와 같은 부모를 가지는 노드의 수를 세어 주면 됩니다.

 

Union-find 알고리즘을 구현하는 가장 대표적인 방법으로 크루스칼 알고리즘이 있습니다. 이를 이용하여 간단히 구현하였습니다.

 

 

채점 결과

Java 문법에 점차 익숙해지는 중입니다.

언젠가 코딩 테스트나 알고리즘 대회도 Java로 풀 수 있는 날이 오면 좋겠습니다.