알고리즘 풀이/디스조인트-셋
-
백준 4195번 친구 네트워크 :: 마이구미알고리즘 풀이/디스조인트-셋 2017. 11. 12. 20:48
이 글은 백준 알고리즘 문제 4195번 "친구 네트워크" 를 풀이한다.풀이 방법으로는 디스조인트-셋을 통해 진행된다.문제 링크 - https://www.acmicpc.net/problem/4195디스조인트 셋 이해 - http://mygumi.tistory.com/246 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 가입한 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. 노드를 친구로, 간선을 친구 관계라고 생각할 수 있다.친구 관계라는 것은 같..
-
백준 9938번 방 청소 :: 마이구미알고리즘 풀이/디스조인트-셋 2017. 11. 9. 20:55
이 글은 백준 알고리즘 문제 9938번 "방 청소" 를 풀이한다.풀이 방법으로는 디스조인트-셋 자료구조를 이용한다.개인적으로 보면, 굉장히 어려운 문제가 된다.문제 링크 - https://www.acmicpc.net/problem/9938디스조인트 셋 이해 - http://mygumi.tistory.com/246 은기는 술병 N개(1부터 N까지 번호가 매겨져 있다)와 서랍 L개(1부터 L까지 번호가 매겨져 있다)를 가지고 있다. 술병은 은기의 방 바닥에 흩어져 있고, 어린이날을 맞이해 방 청소를 하려고 한다. 서랍에는 술병이 하나 들어갈 수 있다. 나중에 원하는 술을 빠르게 찾을 수 있게 하기 위해 은기는 각각의 술병이 들어갈 수 있는 서랍의 번호 Ai와 Bi를 공책에 적어 놓았다.은기는 술병을 1번부터..
-
백준 1717번 집합의 표현 :: 마이구미알고리즘 풀이/디스조인트-셋 2017. 11. 5. 22:23
이 글은 백준 알고리즘 문제 1717번 "집합의 표현" 을 풀이한다.문제는 디스조인트-셋(disjoint-set)을 이용하여 해결할 수 있다.문제 링크 - https://www.acmicpc.net/problem/1717디스조인트-셋 이해 - http://mygumi.tistory.com/246 초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.집합을 표현하는 프로그램을 작성하시오. 이 문제는 디스조인트-셋에 대해 기초를 다지기 위한 가장 기본적인 문제가 된다.0일 때, 유니온(union) 을 호출하고, 1일 때, 파인드(find) 를 호출하면 된다. 다음 예제를 통해 ..
-
백준 10775번 공항 :: 마이구미알고리즘 풀이/디스조인트-셋 2017. 11. 5. 00:34
이 글은 백준 알고리즘 문제 10775번 "공항" 을 풀이한다.문제 풀이는 유니온-파인드(union-find) 또는 디스조인트-셋(disjoint-set) 이라고 불리는 자료구조를 이용한다.유니온-파인드 이해 - http://mygumi.tistory.com/246문제 링크 - https://www.acmicpc.net/problem/10775 오늘은 신승원의 생일이다.박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 도킹된 게이트에는 다른 비행기가 도착..