백준/그래프83 백준 11657 c++ "타임머신" -PlusUltraCode- https://www.acmicpc.net/problem/11657 [필자 사고]음수의 가중치와, 사이클이 존재할 수 있는 가능성 + 최단거리를 묻는 문제 즉 벨만포드 알고리즘을 사용해야 된다. 벨만 포드 알고리즘 이용시 주의할 점은 충분히 많은과정을 반복해야 된다.아래의 코드처럼 1~N-1까지 반복하는 과정이다. 다음으로 마지막에 음수 사이클이 존재하는 지를 확인하기 위해 한번만 더 배열을 탐색하는 과정이 필요하다. 알고리즘의 시간복잡도는 O(VE)다. 모든 노드와 모든 간선을 탐색하기 때문이다. Input() 함수이 함수는 노드와 간선의 정보를 입력받는 역할을 한다.먼저 노드 수 N과 간선 수 M을 입력받고, 각 노드의 최단 거리를 저장하는 Distance 벡터를 초기화한다.이후 M개의 간선 .. 2024. 9. 5. 백준 1854 c++ "K번째 최단경로 찾기" -PlusUltraCode- https://www.acmicpc.net/problem/1854 [필자 사고] 이 문제를 리뷰해보자면 다익스트라 알고리즘을 이용하여 최단거리를 구하는 문제의 변형이라고 생각한다.그동안 최단거리의 경로만 구해왔었지만 이 문제만의 특별한 점은 K번째 최단거리라는 점이다.그러한 이유로 기존 int Distance[] 를 이용했던 필자는 우선순위 큐 List 를 사용하여 문제를 해결했다.arr는 정방향 그래프를 저장하는 2차원 벡터이다. arr[s]는 s 노드에서 갈 수 있는 다음 노드와 그 간선의 가중치(시간)를 저장한다.pqList는 각 노드에서 K번째 최단 경로를 저장하는 우선순위 큐(최대 힙)를 저장하는 벡터다.pqList[nextNum]는 nextNum 노드까지의 K번째 최단 경로들을 저장한다. vi.. 2024. 9. 4. 백준 1916 c++ "최소비용 구하기" -PlusUltraCode- https://www.acmicpc.net/problem/1916 [필자 사고] 먼저, Input 함수는 그래프의 노드 수(N)와 간선 수(M)를 입력받고,그래프를 저장할 2차원 벡터 arr, 각 노드까지의 최단 거리를 저장할 벡터 Distance,그리고 각 노드의 방문 여부를 기록할 벡터 visited를 초기화한다.그래프의 간선 정보를 입력받아 arr에 저장하며, 시작점과 끝점의 인덱스도 입력받는다. 그 다음, BFS 함수는 다익스트라 알고리즘을 사용하여 시작점에서 끝점까지의 최단 거리를 계산한다.이 함수는 우선순위 큐를 사용해 시작점에서 출발하여 다른 노드로 가는 최단 경로를 탐색한다.우선순위 큐에서 꺼낸 노드에 대해, 그 노드에서 연결된 다음 노드로 가는 경로를 계산하여,더 짧은 경로가 발견되면 .. 2024. 9. 3. 백준 1753 c++ "최단경로" -PlusUltraCode- https://www.acmicpc.net/problem/1753 [필자 사고]먼저, 입력을 처리하는 함수가 있다.이 함수는 노드의 수, 간선의 수, 시작 노드 번호를 입력받고,정방향 그래프를 저장할 2차원 벡터 arr, 방문 여부를 기록할 벡터visited, 그리고 각 노드까지의 최단 거리를 저장할 벡터 Distance를 초기화한다.초기화 과정에서 Distance 벡터는 매우 큰 값으로 채워지는데,이는 아직 어떤 노드까지의 최단 거리가 계산되지 않았음을 의미한다. 다음으로, BFS(우선순위 큐를 활용한 다익스트라 알고리즘)를 수행하는 함수가 있다.이 함수는 우선순위 큐를 사용해 시작 노드에서 출발하여, 다른 모든 노드까지의 최단 거리를 계산한다.알고리즘은 각 노드에 대해 현재까지 계산된 최단 거리가 더.. 2024. 9. 3. 이전 1 2 3 4 5 6 7 8 ··· 21 다음
