Traveling Programmer

문제https://www.acmicpc.net/problem/1719풀이(32분)import java.io.*;import java.util.*;public class Main { static int n, m; static int[][] floyd; static int[][] idx; static boolean[][] edges; static final int MAX = 1_000_000_000; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTok..

문제https://www.acmicpc.net/problem/2610풀이(39분)import java.io.*;import java.util.*;public class Main { // union-find를 통해 위원회 수 및 속한 인원을 구한다 // floyd 행렬 내에서 의견 전달 시간의 최솟값을 구한다. // 만약 동일한 시간을 갖는 대표가 있다면 한명이면 된다. // 이 최솟값을 만들 수 있는 사람이 그 위원회의 대표가 된다. // 이 인덱스를 List에 넣고, 오름차순으로 출력한다. static int n; // 회의에 참석하는 사람의 수 static int[] union; // 위원회 static int[][] floyd; // 최단 거리 sta..

문제https://www.acmicpc.net/problem/11403풀이(7분)import java.io.*;import java.util.*;public class Main { static int n; static boolean[][] floyd; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; n = Integer.parseInt(br.readLine()); // 정점의 개수 floyd = new boolean..

문제https://www.acmicpc.net/problem/11404풀이(12분)import java.io.*;import java.util.*;public class Main { static int n, m; static int[][] floyd; static int INF = 1_000_000_000; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; n = Integer.parseInt(br.readLine()); /..

플로이드-와샬 알고리즘이란?플로이드-와샬(Folyd-Warshall) 알고리즘그래프의 최단 경로를 구하는 알고리즘 중 하나모든 정점들 간의 최단 거리를 구함(테이블을 채운다고 볼 수 있음)음수 사이클이 없어야 함 (음수 가중치는 허용)그래프 비용 인접 행렬로 표현되어 있다고 가정시간 복잡도 O(n^3)동적 계획법(dp) 이용원리경유지 k, 출발 정점 i, 도착 정점을 j라고 하자. 그래프의 연결 경로 graph라는 이차원 배열에 저장되어 있다.graph[i][j]는 i에서 j까지 가는 최단 거리를 나타낸다.graph[i][k] + graph[k][j]는 i에서 j까지 가는데 k를 경유하여 가는 거리이다.만약, graph[i][j] > graph[i][k] + graph[k][j]면 i부터 j까지 가는데 ..