본문 바로가기

BOJ 문제풀이/최소스패닝트리 (MST)

백준 2887 : 행성 터널 https://www.acmicpc.net/problem/2887 행성터널. 최소스패닝트리 문제이다. 간선의 정보를 주는 것이 아니라 정점의 정보(x, y, z 좌표) 를 준다. 따라서 주어진 정점의 정보를 토대로 후보 간선들을 정해야 하는데 정점 N이 100,000 이므로 N^2 연산으로 모든 행성들을 일일이 다 연결시키면 초과가 발생한다. 따라서 간선의 후보를 주어진 조건에 맞게 적절히 설정해야한다.우선 행성과 행성간의 3차원상에서의 거리가 가중치가 아닌x,y,z좌표 중에서 거리가 짧은것 하나만 가중치가 된다. 또한, 모든 행성을 후보로 연결할 필요 없이 x,y,z 좌표중 행성 가까이에 있는 행성들만 후보터널로 사용하면된다. 예시가 다음과 같이 주어졌다 행성번호 1 2 3 4 5 x , y, z 11.. 더보기
백준 1922 : 네트워크 연결 https://www.acmicpc.net/problem/1922 MST(최소스패닝트리)의 가장 기초 문제이다. kruskal 알고리즘 대신 prim 알고리즘을 이용해서 풀어보았다. kruskal 알고리즘은 작은 간선들 부터 차례로 확인해보면서그 간선을 연결하면 cycle이 도는지 확인하는 알고리즘이다.이 때 union-find를 사용하여 재귀적으로 각 정점의 뿌리정점을 정의해주어서로가 연결되어있는지의 여부를 확인한다. 반면, prim 알고리즘은 한 정점을 기준으로 최소 간선을 따라다음 정점를 탐색해나간다. 정점을 하나씩 탐색할때마다새로 탐색한 정점에 연결되어 있던 유효한 간선들을 priority_queue에 넣는다.이는 한정점을 탐색하고 다음 최소 간선은 priority_queue에 넣어놓은 top().. 더보기
백준 10423 : 전기가 부족해 https://www.acmicpc.net/problem/10423 Union-Find를 살짝 응용한 문제.최소 스패닝 트리이되 무조건 모든 노드가 연결이 되는 문제가 아니다. 모든 도시가 연결되어있을 필요는 없고 다만 모든 도시가 발전소와 연결되어 있기만 하면 된다.발전소를 보유하고 있는 도시 가 주어지므로 발전소를 -1로 두었다. 뿌리노드 배열을 -1로 두고 최종적으로 모든 노드의 뿌리노드가 -1이 되면 발전소와 연결이 된 것이다.예시를 참고하자면 1,2,9번 도시가 발전소를 보유하고 있으므로 다음과 같이 설정하고 시작해준다. * vRoot[][1,2,3,4,5,6,7,8,9]-> [-1,-1,3,4,5,6,7,8,-1] ... -> [-1,-1,-1,-1,-1,-1,-1,-1,-1] 이 되면 연결완.. 더보기
백준 1774 : 우주신과의 교감 https://www.acmicpc.net/problem/1774 기본적인 MST 문제이다. 간선이 주어지지 않고 정점의 x,y좌표가 주어졌는데 정점의 개수가 1000개라모든 정점을 연결하는 후보 간선을 뚫어도 N^2연산으로 충분히 가능하다. 단 조금의 차이점은 미리 다리를 놓은 것인데, 이 경우 연결된 간선의UnionFind 에서 merge작업만 수행해주면 된다. 즉 각 노드의 루트노드끼리 병합을 수행해주고 일반적인 Kruskal을 진행하기만하면 된다. 이후 Kruskal을 진행할때 이미 연결한 간선이 나오더라도 이미 root노드가 병합이 되었으므로그냥 무시하고 넘어가기 때문이다. ※ 단, 부동소수점에 관하여..보통 소수점 자리수를 맞출때 setprecision을 사용했다.그러나 이문제에서 setpre.. 더보기
백준 2463 : 비용 https://www.acmicpc.net/problem/2463 쉽지 않은 문제였다... 단 이 과정에서 해당 노드가 속해있는 최상단 뿌리노드 외에 배열을 하나 더 설정해주어야 하는데 그 뿌리노드에 속한 노드들의 개수를저장해주어야 한다. 만약 vRoot[] 가 1,2,3,4,5,6 이면 임의로 groupSize[] 의 변수를 만들고 각 노드그룹이 속한 개수 1,1,1,1,1,1 로 초기화 시켜준다.3과 6이 합병되면 3,6의 vRoot는 3으로 통일이 된다. 그럼 이때 3번노드는 3과 6 두개의 노드를 가지고 잇는 뿌리노드이므로 groupSize[3] = 2가 되어야한다 이는 본래 groupSize[3] 의 값인 1에다가 6의 뿌리노드(6 자신)의 개수 groupSize[6]의 값 1을 합친 2가 되는.. 더보기
백준 4386 : 별자리 만들기 https://www.acmicpc.net/problem/4386 MST 문제에 있어 입력정보에 애초에 간선에 대한 정보와 가중치가 주어진다면 쉽지만꼭 간선에 대한 정보가 주어지지 않을 수도 있다.노드에 대한 정보가 주어지고 그 정보를 토대로 간선 후보를 추출해야 한다. 이 문제의 경우 간선 후보가 될 수 있는 최대 경우의 수가 100*100으로 최대 10만번 연산밖에 안되기때문에간선 후보를 모든 행성이 연결된 것으로 할 수 있다.먼저 별에대한 입력정보를 받고 별을 n^2 연산으로 간선을 만들고 Kruskal 알고리즘 적용한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 .. 더보기
백준 13418 : 학교 탐방하기 https://www.acmicpc.net/problem/13418 Kruskal 알고리즘을 이용한 풀이단 최소 스패닝 트리 뿐만 아니라 최대 스패닝트리도 동시에 구현해주어야 한다.Sort() 를 오름차순과 내림차순 두번 구현하는 것 보다 그냥 오름차순으로 한번 sort해주고 최대 스패닝트리를 구할때 reverse_iterator 를 이용해 Unionfind 하여 시간을 단축시킬 수 있었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 .. 더보기
백준 1197 : 최소 스패닝 트리 https://www.acmicpc.net/problem/1197 MST 기본문제. UnionfindfindRoot 할때 메모이제이션하는것 잊지말자.현재 노드에서 재귀적으로 갈 수 잇는 최대 root를 바로 vRoot에 저장하면속도를 훨씬 줄일 수 있다. Kruskal은 항상 작은 비용이 드는 간선부터 확인해보되간선이 연결하고 있는 두 노드 i 와 j 가 이미 연결되어있나 확인하고연결이 안되어있을때 연결시켜준다. 연결여부 확인은 서로의 루트노드를 재귀적으로 따라가서 그 결과루트노드가 같은지 여부를 확인하는 것이다. 연결해주는 것은 서로의 루트노드에 상하관계를 만들어주는 것이다.j 의 최상단 루트의 루트를 i 의 최상단루트로 처리한다.따라서 현재 i 와 j 를 포함한 모든 노드들의 최상단 루트는 i 의 최.. 더보기

티스토리툴바