전체 글

문제https://www.acmicpc.net/problem/23286백준 문제집 - 0x1C강 - 플로이드 알고리즘알고리즘: 그래프 이론, 최단 경로, 데이크스트라, 플로이드-워셜풀이 출발노드를 A, 도착노드를 B라 했을때 A에서 B로 가는 경로는 여러가지가 될 것이다.각 경로(A-K-B)에서 가장 높은 허들을 h라 했을때, h1, h2, h3... 중 가장 작은 값이 A-B 경로의 값이 되는것이다. 만약 graph[A][K]의 높이가 3, graph[K][B]의 높이가 6이라면 A-K-B의 경로는 6이 된다.이런식으로 모든 정점 K를 중간 노드로 두고 각 경로마다 가장 높은 허들을 체크한다.(기존 graph[A][B]값이 4라면 4 이니 갱신하지 않고 그대로 두는 식.) 참고로 이 문제... 예전에 ..

문제https://www.acmicpc.net/problem/13314백준 문제집 - 0x1C강 - 플로이드 알고리즘알고리즘: 그래프 이론, 해 구성하기, 최단 경로, 플로이드-워셜풀이처음 접하는 유형이라 굉장히 당황스러웠던 문제... 다른 풀이 + GPT를 참고해서 풀었다.결론부터 말하자면 9700개 이상의 차이가 발생하는 "데이터"를 찾아야 하는 문제다.일단 지구이씨의 코드는 파일로 첨부되어 있는데, 살펴보면 아래와 같다.# 조건if( i == j && D[i][j] != 0 || D[i][j] > 10000) WRONG;# 첫번째 코드for(int k = 1; k 중간 거점 노드 k의 범위를 1 ~ N으로 설정해야 하는데, N-1까지만 확인한다.즉 D[i][N] + D[N][j]의 경우를 아예 체크..

문제https://www.acmicpc.net/problem/1719백준 문제집 - 0x1C강 - 플로이드 알고리즘알고리즘: 그래프 이론, 최단 경로, 데이크스트라, 플로이드-워셜풀이최단경로를 구해야 하니 플로이드 워셜은 필수고, 추가로 경로표(다음에 방문할 노드)도 구해야 한다.(11780: 플로이드 2를 풀어봤다면 쉬운 문제다.) 먼저 최단경로용 리스트 / 경로 저장용 리스트를 따로 생성해야 한다.각 리스트는 다음과 같이 구성 될 예정이다.graph[a][b]: a에서 b로 가는 최단거리nxt[a][b]: a에서 b로 갈 때, a 다음으로 방문할 노드 (a, b)가 같은 중복 데이터는 주어지지 않으니 입력 데이터 그대로 리스트에 저장해주면 된다.graph[a][b] = cnxt[a][b] = b 그리..

문제https://www.acmicpc.net/problem/1507백준 문제집 - 0x1C강 - 플로이드 알고리즘알고리즘: 그래프 이론, 최단 경로, 플로이드-워셜풀이 모든 A-B(B-A)는 연결되어있다.(직접 or 우회)주어진 간선들은 모두 최단경로 값이다.단, 갯수는 "최소"가 아니다.일단 주어진 값들로 A-B 쌍의 거리를 구했을때 최단경로를 만족하는지 확인해야한다. 최소 갯수를 만족하는지는 다음 문제다.A-B 직행보다 A-K + K-B 우회값이 더 크다면 최단경로가 아닌 셈. (같은 경우는 괜찮다)첫번째 조건을 만족하지 못했다면 바로 -1를 출력해주고, 만족했다면 다음 단계로 넘어간다.예제와 함께 보면 이해가 쉽다.꼭 필요한 도로만 남겨두고 나머지는 제거한다. 남겨둔 도로들의 합이 문제에서 말하는..

문제https://www.acmicpc.net/problem/11562백준 문제집 - 0x1C강 - 플로이드 알고리즘알고리즘: 그래프 이론, 최단 경로, 플로이드-워셜풀이 일반적인 최단경로 문제와는 다르게 비용이 아닌 "일방통행"이냐, "양방향"이냐의 정보만 주어진다. 요 점이 포인트다.그리고 "모든 길을 양방향으로 바꿨을경우 이동 불가능한 경로는 없다"라고 되어있는데, 아예 이동 불가능한 길은 양방향으로 바꿀 수 없다.a → b든 b → a든 이미 일반통행이 존재했던 경우에만 양방향으로 바꿀 수 있다. 그렇다면 일반통행, 양방향, 막힌 길을 별도로 표시해줘야한다.양방향 길(b=1): 추가 비용 없이 양쪽 모두 이동 가능하므로 0일반통행 길(b=0)정방향: 추가 비용 0역방향: 추가 비용 1(양방향으로 ..

문제https://www.acmicpc.net/problem/1956백준 문제집 - 0x1C강 - 플로이드 알고리즘알고리즘: 그래프 이론, 최단 경로, 플로이드-워셜풀이 두 마을을 왕복하는 경우도 사이클에 포함된다.즉, 플로이드 워셜로 각 마을 사이의 최단거리값을 구한 다음 한 마을을 기점으로 다른 마을까지의 왕복거리를 계산하면 된다.시작마을 A, 도착마을 B일때 A → B의 값 + B → A의 값이 가장 작은 경우를 선택하면 되는 것이다. (일방통행이므로 A-B, B-A의 값이 다르다.) 사실 문제 자체는 어렵지 않다. 단순한 플로이드 워셜 문제에 가깝다.하지만 조건식을 어떻게 작성하는지에 따라 시간초과가 날 수도 있으니 주의해야한다. 전체적인 과정은 아래와 같다.각 마을 사이의 거리를 그래프에 저장...