날마다 새로운 코딩

1. 문제 : https://www.acmicpc.net/problem/1944 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 2. 풀이 : Kruskal + BFS 3. 설명 출발 지점에서 로봇과 복제된 로봇이 열쇠까지 이동하는 최단 거리와, 열쇠가 있는 지점에서 복제된 로봇이 다른 열쇠가 있는 지점까지 이동하는 최단 거리를 표현하면 그림[1]과 같다. 각각의 최단 거리는 S지점과, K지점에서의 BFS로 구할 수 있다. 출발 지점과 열쇠가 있는 지점을 넘버링하여 표현을 하면 ..

Algorithm/Kruskal 2021. 7. 5. 22:19

1. 문제 : https://www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1≤N≤1,000)과 도로의 개수 M(1≤M≤n*(n-1)/2) 이 주어진다. 입력의 두 번째 줄 www.acmicpc.net 2. 풀이 : Kruskal 3. 시간복잡도 : O(ElogE) 4. 설명 문제의 조건은 다음과 같다. 1) 피로도 계산은 최초 조사된 길을 기준으로 한다. 2) 최악의 코스 = 오르막 길이 가장 많은 코스 3) 최적의 코스 = 오르막 길이 가장 적은 코스 각 간선에 오르막길인 경우엔 '0'을 내리막길인 경우엔 '1'의 가중치를 부여하고, 간선들을 가중치..

Algorithm/Kruskal 2021. 6. 21. 23:18

1. 문제 : https://www.acmicpc.net/problem/2406 2406번: 안정적인 네트워크 첫째 줄에 두 정수 n(1≤n≤1,000), m이 주어진다. n은 컴퓨터의 개수이며, m은 연결되어 있는 지사 컴퓨터들의 쌍의 개수이다. 다음 m개의 줄에는 두 정수 x, y가 주어진다. 이는 서로 다른 두 컴퓨터, www.acmicpc.net 2. 풀이 : Kruskal 3. 시간복잡도 : O(ElogE) 4. 설명 문제의 예제는 그림[1]과 같이 표현이 된다. 문제의 조건에서 본사 컴퓨터(1번)는 각 지사의 컴퓨터와연결되어 있는 네트워크를 보유하고 있다. 2번과 3번, 3번과 4번 컴퓨터는 직접 연결되어 있다. 문제에서 네트워크에 고장이 발생하는 경우는 다음과 같다. 1) 직접 연결되어 있..

Algorithm/Kruskal 2021. 6. 19. 23:58

1. 문제 : https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 2. 풀이 : Kruskal 3. 시간복잡도 : O(ElogE) 4. 설명 모든 대학교를 최단 거리로 연결을 해야 하는 문제다. 단, 문제의 조건에따라 남초 대학교와 여초 대학교를 연결하는 도로로만 최단 거리가 구성되어야 하고 모든 대학교를 연결하는 경로가 없을 경우 -1을 출력한다. 그림[1]에서 남초 대학교는 파란색으로 여초 대학교는 빨간..

Algorithm/Kruskal 2021. 6. 19. 22:38

1. 문제 : https://www.acmicpc.net/problem/9373 9373번: 복도 뚫기 각 테스트 케이스마다 센서에 감지되지 않고 복도를 지나갈 수 있는 원형 물체의 최대 반지름을 부동소수점 실수로 한 줄에 출력한다. 물체는 매우 정밀하게 움직일 수 있다고 가정한다. 만약 www.acmicpc.net 2. 풀이 : Kruskal 3. 시간복잡도 : O(N2logN) 4. 풀이 그림[1]과 같이 센서가 배치 되어있다고 생각해보자. 문제 조건에의해 왼쪽벽은 x=0인 직선이 되고, 오른쪽벽은 x=20인 직선이 된다. 각 센서들간의 거리를 '두 점 사이의 거리 - 각 센서의 반지름'으로 구해보면 그림[2]와 같다. 이어서, 각 센서들과 벽과의 거리를 구하면 그림[3]과 같다. 거리가 짧은 순서대..

Algorithm/Kruskal 2021. 6. 14. 22:02

1. 문제 : https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 2. 풀이 : Kruskal 3. 시간복잡도 : O(ElogE) 4. 설명 문제의 조건은 아래와 같다 1. 분리된 두 마을 사이의 길은 없앤다. 2. 각 분리된 마을 안에서 임의의 두 집 사이에 경로는 항상 존재하며, 길은 더 없앨 수 없다. 3. 길의 유지비의 합을 최소로 한다. 분리되기 전 하나의 마을에대해 MST를 생성한다. 완성된 MST에..

Algorithm/Kruskal 2021. 6. 12. 00:24

1. 문제 : https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 2. 풀이 : Kruskal 3. 시간복잡도 : O(ElogE) 4. 설명 kruskal 알고리즘을 사용하여, 최소 스패닝 트리를 만들어 문제를 해결한다. 그림[1]과 같이 가중치 오름차순 순으로 모든 간선들을 우선순위큐에 삽입한다. 우선순위큐에서 간선을 하나씩 빼내면서 union-find를 진행한다. 그림[5]에서 1번 컴퓨터와 2번 컴퓨터는 이미 3번 컴퓨터를 통해 연결되어 동일한 네트워크상에 있으므로, 1번 컴퓨터와 2번 컴퓨터는 연결하지 않는다. 그림[7]에서 2번..

Algorithm/Kruskal 2021. 6. 10. 22:23