푸으름

✏️ 문제 링크 https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 기본적인 플로이드 와샬 구현 문제에서 경유지의 개수와 경유지를 출력하는 문제입니다. 이런 경우에는 방문배열을 하나 더 만들어서 각 경로들의 마지막 경유지를 저장해주어야 합니다. 만약 예를 들어서 1->4의 경로가 있다면 route[1][4] = 1; 이런 식으로 말이죠 그렇게 다 저장을 해주게 되면은 이런식으로 route배열이 저장됩니다. 예를 ..

✏️ 문제 링크 https://www.acmicpc.net/problem/25168 25168번: 게으른 아리를 위한 접종 계획 첫째 줄에 백신의 개수 N (1 < N ≤ 10,000)와 백신들의 선행관계 개수 M (1 ≤ M < 100,000)가 주어진다. 둘째 줄부터 M+1번째 줄까지 총 M개의 줄에 각 선행관계의 정보가 세 개의 정수 S,E (1 ≤ S < E ≤ N), www.acmicpc.net ✏️ 문제 풀이 위상정렬을 이용해서 풀었고 백신의 유효기간에 주의하여서 문제를 접근하였습니다. 이 부분에서 경우의 수가 나눠지게 됩니다. 두 백신간의 최소 대기기간이 일주일 이상 넘어가게 되는 경우와 그렇지 않은 경우로 나누어서 풀어야 합니다. 이것만 주의한다면 일반적인 위상정렬 문제와 다를게 없습니다...

Algorithm 공부 #18 - 그래프(최소 신장 트리) 최소 신장 트리(minimum spanning tree) ● 그래프에서 모든 노드를 연결할 때 사용한 에지들의 가중치의 합을 최소로 하는 트리 ● 사이클이 포함되면 최소 가중치를 계산할 수 없으므로 사이클을 포함시키지 않는다 ● N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 N-1개 ● 최소 신장 트리 구현 방법 1. 에지 중심으로 저장하므로 에지 리스트로 그래프 표현, 사이클 표현을 위해 유니온 파인드도 함께 사용 2. 그래프를 가중치를 기준으로 오름차순 정렬 3. 가중치가 낮은 에지부터 연결하기(이때 바로 연결하지 않고 두 노드의 사이클 여부를 판단해야 함) 4. 사이클이 생성되지 않는다면 두 노드를 연결, 사이클이 생기면 연..