알고리즘 (PS)/BOJ
[백준] 1043 - 거짓말 (분리집합 풀이)
https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 분리집합 (유니온-파인드)를 사용하여 푸는 문제이다. 문제 분류를 보면 그래프 탐색으로도 분류가 되어있는데, 우선은 분리집합으로 풀어보았다. 이 문제는 시간제한도 2초로 넉넉한데, 파티당 인원수, 파티수, 총 사람 수가 매우 작다. 그래서 시간복잡도는 거의 신경쓰지 않고.. 그냥 최대한 되는 대로 풀어보았다. 풀이 아이디어 1. 분리집합 자료구조만 이해했다면 문제 해결 아이디어를 떠올리는 것은 어렵지 않다...
