최단경로 - 3
Floyd-warshall 알고리즘 : all to all - 가중치 방향 그래프 G=(V,E), V={1,2,...,n} - 모든 노드 쌍들간의 최단경로의 길이를 구함 - d^k[i,j] : 중간에 노드집합 {1,2,...,k}에 속한 노드들만 거쳐서 노드 i에서 j까지 가는 최단경로의 길이 i와 j가 바로 연결 첫 번째 : 연결 두 번째 : 연결 x n개의 노드가 있으므로 i에서 j로 갈 때 n개의 노드를 거쳐서 감 k를 거치지 않고 간다면 d^k-1[i,j] k를 거쳐서 간다면 d^k-1[i,k] + d^k-1[k,i] 따라서 위의 두 값 중 최솟값을 고르면 된다. 수도코드 - 1 수도코드 - 2 경로 찾기 - 파이 이차원 배열을 만들어준다 - k를 거쳐서 가게 된다면 파이 배열에 k를 넣어준다 경..
2021. 3. 30.
[백준7569] 토마토 [java]
이전에 풀었던 토마토 문제와 비슷하지만 새로운 메소드를 만들지 않고 while문을 통해 풀었다. 또한 3차원으로 생각하고 문제를 풀었다. 상,하,좌,우,위,아래 총 6부분을 생각하면 된다 코드 package baekjoon; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class tomato2 { static int[] dx = {-1,0,1,0,0,0}; static int[] dy = {0,1,0,-1,0,0}; static int[] dz = {0,0,0,0,-1,1}; public static void main(String[] args) { Scanner sc = new Scanner(Sy..
2021. 3. 27.
