푸으름

✏️ 문제 링크https://www.acmicpc.net/problem/1738 1738번: 골목길첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과 골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다. 이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로 주어www.acmicpc.net ✏️ 문제 설명  ✏️ 문제 풀이벨만-포드 알고리즘을 이용하는 문제입니다. 처음에는 문제를 대충 읽고 벨만-포드를 돌린 후 음수 사이클의 여부에 따라서 정답을 출력하려고 했으나 문제를 다시 읽어보니 금품의 양이 최대가 되어야 한다는 점을 깨달았습니다. 그래서 방식을 고민하다가 입력받는 가중치를 음의 부호를 붙여서 입력받는 방식을 생각했습니다. 이렇게 하게 되..

✏️ 문제 링크 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 일반적으로 벨만-포드 알고리즘은 방문하는 노드의 거리배열값이 MAX라면 무시하고 지나가지만 이 문제의 경우에는 틀리게 됩니다. 자세한 내용은 아래 링크를 타고 들어가시면 될 것 같습니다. 시작점부터 도착점까지의 거리가 MAX가 아닌 dist[i]의 값이 i를 방문하지 않았다~라는 의미로 해석해야 됩니다 https://www.acmicpc..

Algorithm 공부 #17 - 그래프(벨만-포드 / 플로이드 워셜) 벨만-포드 알고리즘(Bellman-ford-moore Algorithm) ● 그래프에서 최단거리를 구하는 알고리즘 ● 음수 가중치 에지가 있어도 수행가능 ● 시간 복잡도 O(VE), 음수 사이클 여부 판단 가능 ● 벨만-포드 구현 방법 1. 에지 중심으로 동작하므로 그래프를 에지 리스트로 표현(tuple로 출발지점, 도착지점, 가중치 삽입) 2. 최단 거리 배열을 초기화(출발 지점은 0으로, 나머지는 무수히 큰 값으로 초기화) 3. 최단 거리 배열에서 값이 가장 작은 노드를 고르기(일반적으로 출발 노드), N-1번 에지 사용 횟수를 반복하기 4. 선택된 노드에 연결된 에지의 값을 바탕으로 다음 노드의 값을 업데이트 최단거리 업데이트 ..