1. 풀이 더보기 시작점, 열쇠가 있는 모든 지점에서 로봇이 복제되고, 모든 열쇠를 얻어야 하며, 이때 모든 로봇의 이동거리를 구한다. 위의 문제가 MST문제임을 알면 구현은 매우쉽게 일반적인 MST를 푸는것과 같이 하면 된다. 하지만 위의 문제 MST문제인지를 알기가 어렵다. 따라서 조건을 어느정도 외워두고 비슷한 상황에서 MST를 떠올릴 줄 아는것이 중요해 보인다! 2. 소스코드 from collections import deque import sys dR=[0,0,-1,1] dC=[1,-1,0,0] N,M=map(int,input().split()) L=[] for i in range(N): L.append(list(input())) def dist(sR,sC,fR,fC): q=deque([[sR,..

1. 풀이 일반적인 mst문제이고, N개의 노드를 모두 연결하는 edge를 만들어서(nC2개) 크루스칼을 적용하면 정답은 맞지만 시간초과가 발생한다. (소스코드1)​ 시간초과를 줄일 수 있는 방법은 아래의 조건을 이용해서 사용하는 edge의 개수를 줄이는것. (소스코드2) 더보기 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 그리고 위조건을 이용하는 방법은 아래와 같다. (1) 1차원 좌표에서 N개의 점이 있고, 이때 N개의 점으로 mst를 만드는 방법은 왼쪽부터 i번째 점을 i+1번째 점과 연결해나가는 방법이다. (n-1개) (2) 3차원에서도 똑..

모든 노드들을 최소한의 비용으로 연결한 트리를 최소신장트리(mst)라고 한다. 최소신장 트리를 만드는 방법은 여러가지가 있다. ​ 1. 크루스칼 알고리즘 1) 모든 간선들을 오름차순으로 정렬한다. 2) 가중치가 작은 간선부터 하나씩 연결한다. 3) 간선을 연결했을 때 사이클이 생기면 해당 간선은 제거하고 다음 간선을 붙인다. 4) 간선의 개수가 (node개수 - 1)이 될때까지 간선을 이어붙인다. ​ https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221230994142&proxyReferer=https%3A%2F%2Fwww.google.com%2F 18. 크루스칼 알고리즘(Kruskal Algorithm) 이번 시간에 다루어 볼 내용은 바로 크루스..