live the life you love

Floyd-Warshall Floyd-Warshall은 모든 정점에 대해 모든 다른 정점에 대한 최단 경로를 다 구하는 것이다. 또한, 음수 가중치의 경우도 구할 수 있다. 알고리즘은 비교적 간단하다. 관련 문제 백준 11404번 플로이드 기본 개념 3중 for loop 사용 방향, 무방향 그래프 둘다 사용가능, 사이클이 생기면 안된다 음의 가중치 적용 가능 a->b로 가는 최단거리가 a->c->b보다 크면 그 값을 갱신한다 아래의 조건문이 핵심이다 if (arr[i][k] + arr[k][j] < arr[i][j]) { // k를 거쳐가는게 더 작으면 arr[i][j] = arr[i][k] + arr[k][j]; // arr[i][j] 값 갱신 } 시간 복잡도 O(n^3) floyd 구현 각 반복문의 ..

www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 기본적인 BFS에 방문했던 경로를 따로 저장하여 경로를 역순으로 탐색하는게 추가된 문제였다. 수빈이가 갈 수 있는 3가지 경로을 모두 큐에 같이 저장하고 해당 경로마다 탐색을하면 분명 시간초과 또는 메모리 초과가 발생할 것이다. 기본적으로 수빈이가 이미 갔던 경로는 파악하기 위해서는 bool 타입의 visited 배열로 단순히 방문체크만 해주는 것에 한가지를 더 추가해야한다. ..