Skip to content

Latest commit

 

History

History
308 lines (251 loc) · 8.18 KB

9회차_2022.07.06_플로이드.md

File metadata and controls

308 lines (251 loc) · 8.18 KB

플로이드

image

강지웅

func 플로이드() {
    let n: Int = Int(readLine()!)!
    let m: Int = Int(readLine()!)!
    var minCosts: [[Int]] = [[Int]](repeating: [Int](repeating: 2_000_000_000, count: n + 1), count: n + 1)
    
    for i in 1...n {
        minCosts[i][i] = 0
    }
    
    var input: [Int]
    for _ in 0..<m {
        input = readLine()!.split(separator: " ").map { Int($0)! }
        if minCosts[input[0]][input[1]] > input[2] {
            minCosts[input[0]][input[1]] = input[2]
        }
    }
    
    for k in 1...n {
        for i in 1...n {
            for j in 1...n {
                if i == j || i == k || j == k {
                    continue
                }
                
                if minCosts[i][j] > minCosts[i][k] + minCosts[k][j] {
                    minCosts[i][j] = minCosts[i][k] + minCosts[k][j]
                }
            }
        }
    }
    
    for i in 1...n {
        for j in 1...n {
            if minCosts[i][j] < 2_000_000_000 {
                print("\(minCosts[i][j])", terminator: " ")
            } else {
                print("0", terminator: " ")
            }
            
        }
        print("")
    }
}

김진산

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

//BOJ_11404_플로이드
class Main{

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int n = Integer.parseInt(st.nextToken()); //도시수
        int m = Integer.parseInt(br.readLine()); // 버스 수

        int map[][] = new int[n+1][n+1]; // 거리 정보
        for (int[] d : map){
            Arrays.fill(d, Integer.MAX_VALUE);
        }

        for (int i = 0; i<m; i++){ //거리 정보 입력
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            map[a][b] = Math.min(map[a][b], c);
        }

        for (int k = 1; k<=n; k++){ //경유지
            for (int i = 1; i<=n; i++){ //출발지
                if (i == k) continue;
                for (int j = 1; j<=n; j++){ //목적지
                    if (j == i || j == k) continue;
                    if (map[i][k] != Integer.MAX_VALUE && map[k][j] != Integer.MAX_VALUE)
                        map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]); //더 작은 값으로
                }
            }
        }

        //출력
        for (int i = 1; i<=n; i++){
            for (int j = 1; j<=n; j++){
                if (map[i][j] == Integer.MAX_VALUE)
                    System.out.print(0 + " ");
                else System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }

        br.close();
    }
}

서예진

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class MinPath {

    static int city, bus;
    static int[][] result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        city = Integer.parseInt(br.readLine());
        bus = Integer.parseInt(br.readLine());

        result = new int[city+1][city+1];

        for(int i = 1; i <= city; i++){
            for(int j = 1; j <= city; j++){
                if(i==j){
                    result[i][j] = 0;
                    continue;
                }

                result[i][j] = 987654321;
            }
        }

        for(int i = 0; i < bus; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            result[a][b] = Math.min(result[a][b], c);
        }

        for(int k = 1; k <= city; k++){
            for(int i = 1; i <= city; i++){
                if(k == i) continue;
                for(int j = 1; j <= city; j++){
                    if(k == j | i == j) continue;
                    result[i][j] = Math.min(result[i][k] + result[k][j], result[i][j]);
                }
            }
        }

        for(int i = 1; i <= city; i++){
            for(int j = 1; j <= city; j++){
                if(result[i][j] >= 987654321){
                    System.out.print("0" + " ");
                }
                else{
                    System.out.print(result[i][j]+ " ");
                }
            }
            System.out.println();
        }
    }

}

오나연

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_BOJ_11404_플로이드_0707 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int max = 987654321;
		
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		
		int[][] map = new int[n][n];
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(i==j) continue;
				map[i][j] = max;
			}
		}
		
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken())-1;
			int to = Integer.parseInt(st.nextToken())-1;
			int cost = Integer.parseInt(st.nextToken());
			
			if(map[from][to] > cost) map[from][to] = cost;
		}
		
		for(int k=0; k<n; k++) {
			for(int i=0; i<n; i++) {
				if(i==k) continue;
				for(int j=0; j<n; j++) {
					if(j==k || j==i) continue;
					if(map[i][j] > map[i][k] + map[k][j])
						map[i][j] = map[i][k] + map[k][j];
				}
			}
		}
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				int tmp = map[i][j];
				if(tmp>=max) tmp = 0;
				System.out.print(tmp + " ");
			}
			System.out.println();
		}
	}
}

이주형



정윤영


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_11404 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());    //도시 개수
        int M = Integer.parseInt(br.readLine());    //버스 개수


        int[][] map = new int[N+1][N+1];
        for(int i=1; i<=N; i++){
            Arrays.fill(map[i], 987654321);
        }


        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            map[from][to] = Math.min(cost, map[from][to]);
        }

        //플루이드-와샬 -> 경출도
        for(int i=1; i<=N; i++){        //경유지
            for(int j=1; j<=N; j++){        //출발지
                if(i==j){
                    continue;
                }
                for(int k=1; k<=N; k++){        //도착지
                    if(j==k || i==k){
                        continue;
                    }
                    if(map[j][k] > map[j][i] + map[i][k]){
                        map[j][k] = map[j][i] + map[i][k];
                    }
                }
            }
        }

        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                if(map[i][j] == 987654321){
                    map[i][j] = 0;
                }
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }

    }
}