판교의 메타몽

문제 링크 The problem link : Geeks For Geeks - Transitive closure of a Graph(클릭) 문제 요약 N*N 배열 graph가 주어집니다. 이 배열은 방향이 있는 그래프를 뜻합니다. graph[i][j]가 의미하는 것은, i 정점에서 j 정점까지 연결되어있는 (= 방향이있는) 간선이 있음을 뜻합니다. 정점 i에서 j까지 (다른 정점을 거쳐서라도) 도달할 수 있는지를 가리키는 그래프를 출력하세요. 핵심 요약 문제 조건을 보면 예상 시간복잡도와 공간복잡도를 이렇게 언급했다. Expected Time Complexity: O(N^3) // 시간복잡도 Expected Auxiliary Space: O(N^2) // 공간복잡도시간 복잡도를 보면 힌트가 나오는데, 이 ..

문제 링크 : www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 문제풀이는 다음과 같다. 1. 모든 도로의 값에 int형 최대값을 삽입한다. 2. 값을 입력 받는다. 3. Floyd-Warshall 알고리즘을 통해 각 간선들끼리 이동값의 최소값을 구한다. 4. 2중 for문을 통해 각 간선들을 왕복하는데 걸리는 최소값을 구한다. 중요한 것은 도로 값의 초기화를 int형의 최대값으로 해줘야 한다는 점이며, 이 문제는 반드시 1번..