728x90 분리집합3 [python] 백준 16724 피리 부는 사나이 https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 문제 해결 safe존을 어떻게 해야 최소로 만들 수 있는지 생각을 해봐야한다. 우선 순환하는 사이클이 있으면 하나를 무조건 만들어야한다는 생각을 가져야한다. 하지만 만약 다른 그룹으로 연결이 될 수 있는 경우도 있다. 예로들면 D L L R D Y U R U 다음과 같은 경우 사이클이 존재하면서 가장 왼쪽 아래있는 'U'는 사이클에 연결이 되므로 safe존은 하.. 2024. 3. 8. [python] 백준 16566 카드 게임 https://www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 문제 해결 이진 분류로 bisect_right를 사용할 수 있는가의 문제 가장 최소의 값을 구할 때 만약 사용했다면 그 다음 수를 찾아야 하는데 여기서도 union-find를 사용하는가에 따라서 시간 단축이 될 수 있다. 만약 이전에 어떤 수를 사용했으면 그 수에 접근 했을 때 다음수로 넘어가도록 union-find를 설계할 수 있기 때문이다... 2024. 3. 5. [python] 백준 16562 친구비 https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 문제 해결 결국 친구 사이클(network)를 만들어서 거기서 친구비 가장 작은 값을 더해주는 문제. 즉 사이클과 그 사이클 안의 가장 작은 친구비를 구하면 된다. CODE import sys input = sys.stdin.readline INF = sys.maxsize sys.setrecursionlimit(10**6) def.. 2023. 4. 13. 이전 1 다음 728x90
