그래프/최소 신장 트리 (3) 썸네일형 리스트형 세부 https://www.acmicpc.net/problem/13905 위의 그림을 순서대로 구현하면 된다. 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)시간 제한이 1초이므로완전 탐색하면 무조건 시간 초과 난다. 숭이에서 혜빈이까지 단방향으로 가면 되는거니까즉, 사이클이 없다. 가중치가 최대로 되게 해야하는최소 신장 트리 문제이다. (뭔가 말이 이상하다) 최소 신장 트리는 "유니온 파인드"로 구현한다. 1. 가중치가 최대로 되게모든 정점을 연결하는 최대 신장 트리를 만든다. 2. 최대 신장 트리를 따라서숭이에서 혜빈이까지 BFS로 경로를 만든다.BFS를 돌리면서 visited 배열에가중치의 최솟값을 저장한다.그러기 위해서 처음의 visited 배열은 INF로 초.. 불우이웃돕기 https://www.acmicpc.net/problem/1414 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net 기부할 수 있는 랜선의 길이의 최대값 = 모두 연결 된 랜선의 최솟값 "최소 신장 트리"로 만들면 되겠다. 문자열 받기 cin.get() cin은 공백이나 개행이 나오면 입력 종료로 간주 cin.get()은 공백과 개행도 입력으로 간주 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 3.. 최소 신장 트리 최소 신장 트리란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 "최소"로 하는 트리. 특징 1. 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다. 2. N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N - 1개다. 1. 에지 리스트로 그래프를 구현하고 유니온 파인드 배열 초기화 에지 리스트는 노드 변수 2개와 가중치 변수로 구성 사이클 처리를 위한 유니온 파인드 배열 배열의 인덱스를 해당 자리의 값으로 초기화 2. 그래프 데이터를 가중치 기준으로 정렬 에지 리스트에 담긴 그래프 데이터를 가중치 기준으로 오름차순 정렬 에지 리스트의 객체를 구조체로 표현하면 operator() 함수를 이용해 정렬을 수행 가능 3. 가중치가 낮은 에지부.. 이전 1 다음
