시나위

1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제 요약 진실을 모르는 파티의 최대 개수 출력 접근 1. union find union find로 풀어야될거같았다. 입력받을 때 같은 파티에 있는 사람들끼리 union 시킨다. for (size_t i = 1; i > length; party[i][0] = length; for (size_t j = 1; j > party[i][j]; if (j == 1) contin..

https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 2월의 첫문제는 union find 문제이다. union에서 같은 부모를 연결하게 될 떄 cycle이 된다. 이를 사용하면 cycle 체크와 union을 같이 진행할수 있다. # import sys; input = sys.stdin.readline def find(a, parent): if parent[a] == a: return a parent[a] = find(parent[a], pare..

https://www.acmicpc.net/problem/7511 7511번: 소셜 네트워킹 어플리케이션 각 테스트 케이스마다 "Scenario i:"를 출력한다. i는 테스트 케이스 번호이며, 1부터 시작한다. 그 다음, 각각의 쌍마다 두 사람을 연결하는 경로가 있으면 1, 없으면 0을 출력한다. 각 테스트 케이스 www.acmicpc.net floyd warshall을 사용해야할까 생각했는데 값이 너무 많아서 다른 방법인 union find로 풀었다. 알고리즘 자체는 어렵지 않았지만 꽤 많이 틀린 문제였다. union-find를 구현하면서 생각보다 많이 틀렸는데 find를 할때마다 값을 갱신하는게 꼭 필요했다. 그 외엔 TC 변수를 i로 둬서 root = [i for i in range(n)] 이랑 ..