최단경로

📖 문제 https://www.acmicpc.net/problem/5972   💡  풀이 방식• 다익스트라 전형적인 다익스트라 문제다,,- 최소 여물 비용 배열을 모두 5만*1000 + 1 이상의 큰 값으로 채운다.- 그래프 정보를 양방향으로 입력받는다.- 시작점 1부터 목적지 N까지 최소 비용으로 이동하도록 다익스트라를 진행한다.  🔺 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778import java.util.*;import java.io.*; public class Main {..

📖 문제 https://www.acmicpc.net/problem/17396   💡  풀이 방식• 다익스트라필요 자료구조- 시야에 보이는지 여부 나타내는 1차원 boolean형 배열- 그래프 인접 리스트- 1 ~ N-1번 분기점이 까지 0번째 분기점까지 가는 데 걸리는 최소 시간 배열 (long형)- 분기점 별 방문 표시를 나타내는 1차원 boolean형 배열  1. 각 분기점이 적의 시야에 보이는지 나타낸다.sight = new boolean[N];st = new StringTokenizer(br.readLine(), " ");for(int i = 0 ; i   2. 1 ~ N-1번 분기점이 까지 0번째 분기점까지 가는 데 걸리는 최소 시간 배열을 모두 최댓값인 Long.MAX_VALUE로 초기화한..

📖 문제 https://www.acmicpc.net/problem/15723   💡  풀이 방식• 플로이드-워셜 i는 k고, k는 j면, i는 j다. - N개의 전제를 입력받으며 a는 b라고 처리한다. → connected[a][b] = true- 플로이드-워셜로 i는 k고, k는 j면, i는 j 가 되도록 처리한다.- M개의 결론이 맞는지 확인하며 a는 b라면(= connected[a][b] == true) T를, 아니라면 F를 출력한다.   🔺 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748import java.util.*;import java.io.*; public class Mai..

📖 문제 https://www.acmicpc.net/problem/1504   💡  풀이 방식• 다익스트라필요 자료구조- 인접 배열 리스트- 시작점에서 각 정점까지 가는 최단 거리 저장용 int형 배열- N개의 각 정점에 대한 boolean형 방문 표시 배열- (목적지, 거리) 정보를 저장하는 객체  1. E개의 입력을 받으며 두 정점 간 거리 정보를 양방향으로 저장한다.2. 꼭 지나쳐야 하는 두 정점 v1, v2를 입력받는다.3. ① 경로 1 > v1 > v2 > N을 지날 때의 최단 거리와, ② 경로 1 > v2 > v1 > N을 지날 때의 최단거리를 계산한다. (다익스트라)4. 두 최단 거리가 모두 최댓값인 INF보다 크거나 같으면, 경로가 없는 것이므로 -1을 출력하고, 그게 아니라면 경로 1..

📖 문제 14497번: 주난의 난(難) 주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다. ‘쿵... 쿵...’ 주난이는 점프의 파 www.acmicpc.net 💡 풀이 방식 • 다익스트라 (우선순위 큐) 최단 경로인 지점을 항상 우선으로 탐색하고자 점프 횟수 기준 오름차순 정렬하는 우선순위 큐를 활용한다. class Node implements Comparable { int x, y, w; public Node(int x, int y, int w) { this.x = x; this.y = y; this.w = w; } @Override public int compareTo(Node n) { // 💥 ..

📖 문제 18243번: Small World Network 첫 번째 줄에 지구에 있는 사람의 수 N과 친구 관계의 개수 K가 주어진다. 모든 사람은 1부터 N까지 번호가 매겨져 있다. (1 ≤ N ≤ 100, 0 ≤ K ≤ N×(N-1)/2) 두 번째 줄부터 K+1번째 줄까지 친구 www.acmicpc.net 💡 풀이 방식 • 플로이드-워셜 - 최단 경로 배열을 모두 큰 값으로 초기화한다. (단, 행과 열이 같은 경우는 0으로 설정) - 입력받은 두 점 간 거리를 1로 설정한다. - 플로이드-워셜을 통해 모든 정점 간의 최소 거리를 구한다. - 7단계 이상인 단계가 존재하는 경우, Big World를 출력한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19..

📖 문제 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 💡 풀이 방식 • 다익스트라 필요 자료구조 - 지름길 정보 저장할 Road 객체 (지름길 시작 위치, 지름길 도착 위치, 지름길 길이) - 지름길 객체 정보 저장할 Road형 배열 - 최단 거리 저장할 int형 배열 . (시작점,도착점,거리)를 저장하는 Road를 생성한다. . Road형 배열에 객체 정보를 저장한다. . 0부터 다익스트라를 진행한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1..

📖 문제 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net 💡 풀이 방식 • 플로이드-워셜 (최단경로) ⇨ 시간 복잡도 : O(N^3) 필요 자료구조 - 각 사람 간 거리 저장할 2차원 int형 배열 - 2차원 배열에 저장할 상수 변수 INF . 값을 입력받으면서 Y면 1을, N이면 INF (=9999) 값을 저장한다. . 플로이드-워셜 통해 친구 연결을 구한다. - 경로를 확인할 세 사람 中 둘 이상이 같은 경우 (출발지=경유지 or 경유지 = 도착지 or 도착지 = 출발지 인 경우), pass한다. - 셋 다 ..

🔺 문제 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 🔺 코드 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 33 34 35 36 37 38 39 import java.util.*; import java.io.*; public class Main { static int N; static int[][] distance; public static void main(String[] args) throws IOException { BufferedRe..