밤이 블로그

BOJ#1219 오민식의 고민 * 문제https://www.acmicpc.net/problem/1219 * 풀이벨만-포드 최단거리 문제입니다. 간선 cost는 음수이고, 각 노드마다 추가로 돈을 벌 수 있습니다.원하는 것은 S(시작점)에서 D(도착점)까지 갈 때 최대로 벌 수 있는 돈의 액수를 구하는 것입니다. 일반적으로 문제에서 간선의 cost가 양수로 주어지는 반면,이 문제에서는 간선 cost가 음수이므로음수 사이클은 문제가 되지 않고 반대로 양수 사이클인 경우가 문제 됩니다. 벨만-포드 알고리즘에 따라 (엣지수(M)만큼 Relaxation)을 N-1번 반복하고N번째에도 Relaxation이 되면 사이클이 존재함을 알 수 있습니다. 그러나 우리는 사이클 유무를 판단하는 것이 목적이 아니라시작점에서 도..

BOJ#1865 웜홀 * 문제https://www.acmicpc.net/problem/1865 * 풀이 벨만-포드 알고리즘을 활용하는 기본 문제입니다. 일단 기본적인 풀이 방법은 "BOJ#11657 타임머신" 문제와 같고,음수 간선 사이클이 존재하는지 확인만 하면 되는 문제입니다. 주의할 점 #1)도로에 방향이 없으므로,도로 정보를 입력 받을 때 양방향으로 생각해야 한다는 점입니다. -> 결국 Edge의 개수는 2 * M + W -> 코드 상 여러번 쓰이게 되므로, 실수하지 않게 따로 변수로 저장해둡시다. 주의할 점 #2)시작점이 주어지지 않았으므로, 시작점을 어느 곳으로 해야 할 지 결정해야 합니다. 음수 사이클은 웜홀이 연결된 지점에서만 존재 할 수 있으므로웜홀의 목적지들을 배열에 따로 저장하여, 이..

벨만-포드 알고리즘(Bellman-Ford algorithm) 최단 경로 알고리즘에서 대표적인 것으로는 1) 다익스트라 : 유향그래프, 한점 - 다수의 점, 음수 가중치 X2) 벨만-포드 : 유향그래프, 한점 - 다수의 점, 음수 가중치 O, 음수 사이클 X3) 플로이드-와샬 : 모든 점- 모든 점 여기서는 벨만-포드 알고리즘에 대해 알아보겠습니다. * 벨만-포드 알고리즘(Bellman-Ford algorithm) 벨만-포드 알고리즘은 가중 유향 그래프에서 최단 경로 문제를 푸는 알고리즘이다. 이때 변의 가중치는 음수일 수도 있다. 다익스트라 알고리즘은 벨먼-포드 알고리즘과 동일한 작업을 수행하고 실행 속도도 더 빠르다. 하지만 다익스트라 알고리즘은 가중치가 음수인 경우에는 처리할 수 없으므로, 이런 경..