그래프 이론 썸네일형 리스트형 백준 세부 13905 https://www.acmicpc.net/problem/13905 13905번: 세부 첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄 www.acmicpc.net 다익스트라를 변형해서 풀면된다. 기존의 다익스트라가 한 정점에서 다른 정점으로의 최단거리를 구한다고 하면 변형된 다익스트라는 한 정점에서 다른 정점으로의 경로중로 이동하는 가중치의 최소값들의 최대값을 구하는 것이다. 예시로 든 그림을 보면 1에서 5로 가는 경로는 총 4가지다. 1) 1-2-3-5 2) 1-7-3-5 3) 1 -7-5 4) 1-7-6-5 각.. 더보기 백준 12850 본대 산책 2 https://www.acmicpc.net/problem/12850 12850번: 본대 산책2 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net N = 10억이므로 시간복잡도가 기존의 O(N)인 알고리즘 또한 먹히지 않는다. (물론 10억 개수의 변수를 메모리 공간에 저장하려고 하면 메모리 초과가 날 것이다.) Vertex 사이의 거리가 모두 같다는 점을 이용해서 그래프의 인접행렬의 거듭제곱을 하면 O(8*8*logN)시간에 경우의 수를 구할 수 있다. package 백준; import java.util.Scanner; public class 본대산책2 { static long map[][]; public static void main(String[] a.. 더보기 이전 1 다음
