알고리즘 - 플로이드 워샬 기본문제. - 플로이드 워샬과 다익스트라의 차이점을 알아야 함. ※ 다익스트라 시간복잡도 : V E logV 플로이드 워샬 시간복잡도 : V^3 다익스트라 : 출발점에서 각 노드들간의 최소 거리. 플로이드 워샬 모든노드들의 최소 거리. * 다익스트라를 노드수 만큼 구했더니 실패한 문제. -> 이유 : 노드가100개 간선이 100000개 라서 100 * 100 * 100000 * log 100 = 시간초과인듯.. * 플로이드 워샬로 풀 경우 100^3 = 1,000,000 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays;..
알고리즘 - 4방탐색 - bfs - 최소값부터 시작하기 때문에 Priority Queue 사용 - 이미 계산한 값은 다음회차에 안해도 되기 때문에 증식한 값만 새로운 list에 저장한 후 큐의 모든 값이 계산되면(1회차) 저장한 리스트를 다시 큐에 넣어줌. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.PriorityQueue; import java.util.StringTokenizer; public class 경쟁적전염_18405 { static int n, k, map[][]; static int[] ..
알고리즘 섬과 섬을 연결할 수 있는 다리의 길이가 최소인값을 찾는 알고리즘 1. dfs탐색을 통해 섬의 정보를 알아야 함. 각각 넘버링 예) 섬이 3개라면 -> 1번섬, 2번섬, 3번섬 2. 섬의 가장자리 즉, 바다와(0) 근접해있는 곳은 bfs탐색을 시작함 - 탐색 기준은 자신의 넘버와 같지않은곳을 따라가면서 탐색(count + 1) - 해당지점의 넘버링값을 보고 자신의 넘버링값과 다르다면 최소값을 갱신하고 리턴. 단, 현재의 cnt값에서 -1해줘야 함. - 모든섬이 연결되어 bfs를 돌릴 수 없는 경우도 있을 수 있기 때문에 Ans가 Max값이라면 0 출력! 아니면 Ans값 출력 * bfs를 사용한 이유 : 최소값을 찾는 알고리즘이기 때문 import java.io.BufferedReader; imp..