[BOJ알고리즘, C++]#1865_웜홀, 최다 경로 알고리즘, 길 찾기 알고리즘, 벨만-포드 알고리즘

2024. 2. 6. 21:06· 문제 풀이/BOJ 문제 풀이
목차
  1. #1. 문제
  2. #2. 풀이
  3. 1. 벨만-포드 알고리즘
  4. 2. 웜홀은 '음수 가중치'를 갖는 간선, 도로는 '양수 가중치'를 갖는 간선!
  5. #3. 코드

 

#1. 문제

 

1865번: 웜홀

첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500),

www.acmicpc.net

 


 

#2. 풀이

 

1. 벨만-포드 알고리즘

 

[알고리즘]#2_길 찾기 알고리즘

#1. 개념 1. 길 찾기 알고리즘 [정의] : 길 찾기 알고리즘은 그래프 자료구조에서 출발점에서 도착점 사이의 경로를 탐색하는 알고리즘입니다. 노드와 노드 간 연결 관계를 나타내는 간선으로 구

webddevys.tistory.com

 

벨만-포드 알고리즘은 '음의 가중치'를 포함하는 그래프에서 "단일-출발" 혹은 "단일-쌍" 최단 경로 알고리즘을 찾는 간선 중심의 알고리즘입니다. 벨만 포드 알고리즘은 최단 경로 값을 찾는 값과 더불어 그래프 내 순환 경로에 존재하는 가중치의 합이 음수인 "음수 사이클"을 탐지하는 보조적인 작업을 병행합니다. 벨만-포드 알고리즘의 주요 포인트는 N-1번 간선 목록을 순회하며, 최단 경로 값을 업데이트한 후, 추가적으로 한번 더 간선 목록을 순회하며 최단 경로 값의 갱신 여부를 확인하여, 기존의 최단 경로 값이 다시 경신될 경우 그래프 내 음수 사이클 여부가 존재하는 것으로 간주합니다.

 

2. 웜홀은 '음수 가중치'를 갖는 간선, 도로는 '양수 가중치'를 갖는 간선!

  1. 간선 목록을 구성합니다.
  2. 벨만-포드 알고리즘을 통해 N-1번 간선 목록을 순회하며 최단 경로 값을 갱신합니다.
  3. 마지막 한 번의 간선 목록 순회를 통해 최단 경로 값 경신 여부를 체크하고, 해당 값이 경신될 경우 음수 사이클 여부를 확신하고 "NO"를 출력합니다!

 


 

#3. 코드

 

#include <iostream>
#include <string>
#include <vector>

#define MAX 30'000'000

using namespace std;

int n, m, w;

struct edge {
	int s, e, t;
};

// 벨만-포드 알고리즘, 시작 정점은 무작위로 임의의 정점으로 설정해도 문제가 없습니다.
bool time_travel(int n, vector<edge> edges) {
	vector<int> dist(n + 1, MAX);

	int s, e, t;

	dist[1] = 0;
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < edges.size(); j++) {
			s = edges[j].s;
			e = edges[j].e;
			t = edges[j].t;
			if (dist[e] > dist[s] + t) {
				dist[e] = dist[s] + t;
			}
		}
	}
	for (int j = 0; j < edges.size(); j++) {
		s = edges[j].s;
		e = edges[j].e;
		t = edges[j].t;
		if (dist[e] > dist[s] + t) {
			return true;
		}
	}

	return false;
}

int main()
{
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);

	int TC;
	cin >> TC;

	int s, e, t;
	while (TC > 0) {
		cin >> n >> m >> w;

		vector<edge> edges;

		for (int i = 0; i < m; i++) {
			cin >> s >> e >> t;
			edges.push_back({ s,e,t });
			edges.push_back({ e,s,t });
		}
		for (int i = 0; i < w; i++) {
			cin >> s >> e >> t;
			edges.push_back({ s,e,-t });
		}

		if (time_travel(n, edges)) cout << "YES\n";
		else cout << "NO\n";

		TC--;
	}

	return 0;
}

 


 

 

 

 

저작자표시 (새창열림)

'문제 풀이 > BOJ 문제 풀이' 카테고리의 다른 글

[BOJ알고리즘, C++]#1766_문제집, 위상 정렬, 그래프  (0) 2024.02.20
[BOJ알고리즘, C++]#11657_타임 머신, 길 찾기, 최단 경로 알고리즘, 벨만-포드, 음수 가중치, 음수 사이클  (1) 2024.02.06
[BOJ알고리즘, C++]#1068_트리, 그래프 탐색, 완전 탐색, 깊이 우선 탐색, DFS  (0) 2024.02.06
[BOJ알고리즘, C++]#11728_배열 합치기, 정렬, 병합 정렬  (0) 2024.02.06
[BOJ알고리즘, C++]#2470_두 용액, 정렬, 퀵 정렬, 투 포인터  (1) 2024.02.05
  1. #1. 문제
  2. #2. 풀이
  3. 1. 벨만-포드 알고리즘
  4. 2. 웜홀은 '음수 가중치'를 갖는 간선, 도로는 '양수 가중치'를 갖는 간선!
  5. #3. 코드
'문제 풀이/BOJ 문제 풀이' 카테고리의 다른 글
  • [BOJ알고리즘, C++]#1766_문제집, 위상 정렬, 그래프
  • [BOJ알고리즘, C++]#11657_타임 머신, 길 찾기, 최단 경로 알고리즘, 벨만-포드, 음수 가중치, 음수 사이클
  • [BOJ알고리즘, C++]#1068_트리, 그래프 탐색, 완전 탐색, 깊이 우선 탐색, DFS
  • [BOJ알고리즘, C++]#11728_배열 합치기, 정렬, 병합 정렬
Hardii2
Hardii2
개발 블로그Hardii2 님의 블로그입니다.
Hardii2
개발 블로그
Hardii2
전체
오늘
어제
  • 분류 전체보기
    • 알고리즘
    • 웹 개발
      • Node.js
      • React
    • 게임개발
      • DirectX12
      • 관련 지식
      • Unreal C++
      • Unreal 블루프린트
    • 언어
      • Effective C++
      • Basic C++
      • 디자인 패턴
      • 자료구조
      • 기술 질문
    • 문제 풀이
      • BOJ 문제 풀이
      • Programmers 문제 풀이
      • geeksForgeeks 문제 풀이
    • 수학
      • 확률과 통계
      • 게임수학
    • 개인프로젝트
    • 그룹프로젝트
      • PM
      • Dev
    • Github

블로그 메뉴

  • 홈
  • 글쓰기

공지사항

인기 글

태그

  • 우선순위 큐
  • 기술 질문
  • dfs
  • unreal
  • 최단 경로
  • 트리
  • 개발
  • programmers
  • 디자인 패턴
  • set
  • BFS
  • BOJ
  • Effective C++
  • Unreal Blueprint
  • 알고리즘
  • stl
  • 정렬
  • C++
  • 그래프
  • DP

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
Hardii2
[BOJ알고리즘, C++]#1865_웜홀, 최다 경로 알고리즘, 길 찾기 알고리즘, 벨만-포드 알고리즘
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.