백준/그래프83 백준 1956 c++ "운동" -[PlusUltraCode] https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net [필자 사고] 처음에는 다익스트라 BFS 벨만포드까지 생각을 해봤다. 정작 이 문제의 해결해야 하는 플로이드 와샬알고리즘은 떠오르지 않았다. 자료를 찾아보니 플로이드 와샬 알고리즘을 사용한 후 사이클이 있는지 없는지 판단하는 법은 Arr[i][k]와 Arr[k][i] 값 둘이 있을 경우 사이클이 생성된것을 알 수 있다. 이 문제를 통해 플로이드 와샬에 개념을 확실.. 2024. 2. 27. 백준 1719 c++ "택배" -[PlusUltraCode] https://www.acmicpc.net/problem/1719 [필자 사고] 다익스트라 혹은 폴로이드 워셜을 이용하여 푸는 문제이다. 필자는 다익스트라를 이용하여 문제를 해결 하였다. 다른 문제와 달리 이 문제의 핵심 포인트는 지나간 경로중 가장 첫번째 경로를 저장해야 된다. 필자는 Union과 find를 이용하여 집합을 이용해 풀었다. 먼저 parent배열에 부모노드를 저장해 주었다. 다익스트라 알고리즘이 끝난 후 parent 배열을 Union 해주어 쉽게 처음 시작한 노드를 찾을 수 있었다. [소스 코드] #include #include #include #include #include #include #include using namespace std; typedef pair Node; vecto.. 2024. 2. 27. 백준 5972 c++ "택배 배송" -[PlusUltraCode] https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net [필자 사고] 문제는 복잡해 보이지만 전형적인 다익스트라 알고리즘을 이용한 최단거리 문제이다 이 부분만 잘 캐치한다면 쉽게 문제를 해결할 수 있을 것이다. [소스 코드] #include #include #include #include #include #include #include using namespace std; typedef pair Node; int N, M; vector Arr; vector p.. 2024. 2. 27. 백준 10282 c++ "해킹" -[PlusUltraCode] https://www.acmicpc.net/problem/10282 [필자 사고] 다익스트라 알고리즘을 이용하면 쉽게 해결할 수 있는 문제이다. 이 문제의 핵심은 관계에 있다. 아무 생각없이 a->b로 그래프를 연결하는게 아닌 b가 감염되면 a는 몇초뒤에 감염된다 라고 써져 있으므로 b->a 형태로 그래프를 만들어 줘야 된다. 이 점만 주의하면 쉽게 해결할 수 있는 문제이다. [소스 코드] #include #include #include #include #include #include #include using namespace std; typedef pair Node; int N, D, C; vector Arr; vector pathLoad; vector visited; int ResultCount =.. 2024. 2. 27. 이전 1 ··· 14 15 16 17 18 19 20 21 다음