union-find3 [Python] 백준 1976번 (여행 가자) 문제 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다. 도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다. 입력 첫 줄에 도시의 수 N이.. 2021. 11. 28. [Python] 백준 10775번 (공항) 문제 오늘은 신승원의 생일이다. 박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다. 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. 공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다. 신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가? 입력 첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다. 두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다. 이후 .. 2021. 11. 25. [알고리즘] 최소 비용 신장 트리(MST) - 크루스칼 알고리즘(Kruskal Algorithm) 신장 트리 (Spanning Tree) 신장 트리란 그래프안에서 모든 정점(노드)을 포함하는 트리이다. 신장 트리는 모든 정점들이 연결되어 있어야 하고, 사이클을 포함하면 안된다. (사이클: 그래프가 순환되어 돌아오는 경로) 신장 트리는 그래프에 있는 n개의 정점을 n-1개의 간선으로 연결하게 된다. 최소 비용 신장 트리 MST (Minimun Spanning Tree) 신장 트리들 중에서 사용된 간선의 가중치 합이 최소인 트리를 말한다. 크루스칼(Kruskal) 알고리즘과 프림 알고리즘이 있다. 크루스칼 알고리즘(Kruskal Algorithm) 그리디 알고리즘을 이용하여 그래프의 모든 정점을 최소 비용으로 연결하여 최적의 답을 구하는 알고리즘이다. 크루스칼 알고리즘 동작 그래프의 간선들을 가중치의 오.. 2021. 11. 10. 이전 1 다음
