어려움 (2) 썸네일형 리스트형 복제 로봇(백준 1944) 시작 지점에서 로봇이 출발하여 키를 모두 갖고와야 한다. 그래서 출발점과 모든 키에 대해서 최소 거리 정보를 저장한 다음에 MST를 실행하면 된다. 최소 거리 정보를 구할 때 bfs를 사용하면 된다. 물대기(백준 1368) 처음에는 만들 우물의 개수를 1부터 생각하면서 각각의 최소비용을 계산하려 했다. 하지만, 우물의 비용이 최소가 된다고 전체 비용이 최소가 되는 보장이 없다. 그래서 다른 블로그의 풀이법을 가져다가 풀었다. 우물을 파는 비용을 해당 번호와 0의 union이라 생각하고 풀어야 한다. import sys input = sys.stdin.readline N = int(input()) edge = [] cost = [] def find_parent(ind): if parent[ind] == ind: return ind parent[ind] = find_parent(parent[ind]) return parent[ind] def union(A,B): x = find_parent(A) y = find_parent(B.. 이전 1 다음