플로이드워셜

📖 문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr   💡  풀이 방식• 다익스트라필요 자료구조- (도착지, 거리) 정보 저장용 인접 리스트- a,b,s에서 시작해서 각 점들까지의 최단 거리를 나타내는 배열- 다익스트라용 우선순위 큐 . a,b,s에서 시작해서 각 점들까지의 최단 거리를 나타내는 배열을 최댓값 (200 * 10만 +1)으로 설정한다.. a,b,s에서 시작해서 각 점들까지의 최단 거리를 구하는 다익스트라를 총 3번 실행한다.  - 현재 번호와 연결된 점들을 지나면서, 현재 연결된 점과 다음 연결된 점까지의 거리를 더한 값이 다음 연결된 ..

📖 문제 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..

📖 문제 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..

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

🔺 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔺 코드 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 import java.util.*; class Solution { public int solution(int n, int[][] results) { int answer = 0; int[][] graph = new int[n + 1][n + 1]; // 인접 행렬 // 이기는 경우의 수 입력 for(int i = ..

🔺 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 🔺 코드 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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 import java.util.*; import java.io.*; public class Main { static int INF = 987654321; // Integer.MAX_VALUE로 하면 틀림 s..

📍 정의 및 특징 모든 노드 간 최단 경로 탐색 - 음수 가중치 에지가 있어도 수행 가능 - DP 원리 이용 (점화식) D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]) : A → B까지 최단 경로를 구할 때, 최단 경로 위에 K가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로 - 노드 개수의 범위가 적은 경우 사용 (∵ 시간 복잡도가 빠른 편이 아니므로) - 시간 복잡도 : O(V³) 📍 필요 변수 1. 최단 거리 배열 2. 인접 행렬 📍 실행 과정 최단 거리 배열 선언 · 초기화 - D[S][E] = if(S == E) ? 0 : ∞ 최단 거리 배열에 인접 행렬 사용해 그래프 데이터 저장 플로이드-워셜 수행 : 점화식으로 배열 업데이트 → 3중 for문 ➕ 예제..

📍 종류 1) BFS - 가중치 X / 단순 최단 경로 탐색 2) 다익스트라 - 가중치 O / 한 노드 기준 모든 노드와의 최단 경로 탐색 3) 플로이드-워셜 - 상관 X / 모든 노드 기준 모든 노드 간 최단 경로 탐색 (사실상 그냥 dp) 4) 벨만 - 포드 - 가중치 O / 특정 출발 노드 → 다른 모든 노드까지의 최단 경로 탐색 (참고) [백준 1753] 최단경로 -Java코드 (Dijkstra)★★★ https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘 bangu4.tistory.com

🔺 문제 1389번: 케빈 베이컨의 6단계 법칙첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻www.acmicpc.net  🔺 코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162import java.util.*;import java.io.*; public class Main {    static int N, M;    static int INF = 10000001;  ..