전체 글 (208) 썸네일형 리스트형 방탈출(백준 23743) 탈출구를 0번으로 가정하고 MST를 만들면 된다. n개의 방에 0번방을 모두 연결해야 하니 총 n개의 길이 필요하다. import sys input= sys.stdin.readline n,m =map(int, input().split()) edges =[] parent=[i for i in range(n+1)] def find(a): if a!= parent[a]: parent[a] = find(parent[a]) return parent[a] def union(a,b): a = find(a) b = find(b) if a< b : parent[b] = a else : parent[a] = b for i in range(m): a,b,c = map(int, input().split()) edges.app.. 복제 로봇(백준 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.. 일감호에 다리 놓기 (백준 17490) 가운데 위치한 섬과 다른 건물들이 모두 이어지면 되는 MST문제이다. 그런데 건물들을 이어주는 길이 끊어진 경우가 있고 건물들 사이의 길이 유지되어 있는 경우가 있다. 그래서 길이 유지된 건물들은 union함수로 같이 묶어줘야 한다. import sys input = sys.stdin.readline n,m,k = map(int, input().split()) arr =[0]+ list(map(int, input().split())) connected = [] if m 슬슬 가지를 먹지 않으면 죽는다(백준 27945) import sys import heapq n,m= map(int, input().split()) parent =[i for i in range(n+1)] edges = [] def find(a): if a!= parent[a]: parent[a] = find(parent[a]) return parent[a] def union(a,b): a = find(a) b = find(b) if a!= b : if a< b: parent[b] = a else : parent[a] = b for i in range(m): a,b,cost = map(int, input().split()) edges.append((cost,a,b)) edges.sort(key =lambda x: x[0]) ways = [] for i .. 도로 (백준 9344) MST를 형성하면 되는데 특정 간선이 MST 형성에 필요한 지 확인만 해보는 문제이다. 크루스칼로 간선들을 확인하면서 미리 입력 받았던 간선이 쓰이는 지 체크한다. import sys import heapq input = sys.stdin.readline test = int(input()) def find(a): if a != parent[a]: parent[a] = find(parent[a]) return parent[a] def union(a,b): a =find(a) b =find(b) if a 돌 게임6(백준 9660) 7번째 돌마다 규칙이 만들어 지니 7로 나눈 나머지로 누가 이길 지 판단한다. n= int(input()) if n%7 ==2 or n%7 ==0 : print("CY") else: print("SK") 안정적인 네트워크 (백준 2406) 전형적인 MST문제인데 첫 컴퓨터를 제외하고 MST를 형성하면 된다. import sys import heapq input = sys.stdin.readline n,m = map(int, input().split()) parent= [i for i in range(n+1)] def find(x): if x != parent[x]: parent[x] = find(parent[x]) return parent[x] def union(a,b): a = find(a) b = find(b) if a 이전 1 ··· 20 21 22 23 24 25 26 다음