graph 검색 결과

해당 글 5건

[BOJ 1504] (Dijkstra)특정 최단 경로(C++)

특정 최단 경로(Gold 4) 문제 전체 문제 보기 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 접근법 이 문제는 양의 가중치를 간선을 가진 그래프에서 최단 경로를 찾는 문제의 변형이다. 출발 노드 1에서 도착 노드 N까지 가는 도중 v1과 v2 노드를 반드시 지나야 한다. 그리고 아래의 그림처럼 1 → v1 → v2 → N으로 가는 경로와 1 → v2 → v1 → N 으로 가는 경로 두 가지가 존재하고 이 둘 중 더 가까운 경로의 거리를 출력해야 한다. 알고리..
Algorithms/Graph 2021. 9. 11. 12:45

[BOJ 1865] (벨만 포드) 웜홀 (C++)

웜홀 (Gold 3) 문제 전체 문제 보기 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 접근법 이번 문제는 음의 가중치가 주어지는 그래프에서 음의 사이클 여부를 파악하는 문제입니다. 간선에 가중치가 없는 그래프에서 최단 경로를 찾기 위해서는 BFS가 가장 효율적입니다. 만약 가중치가 존재한다면 다익스트라 알고리즘을 활용할 수 있습니다. 하지만 다익스트라 알고리즘은 반드시 모든 가중치는 양수가 보장되어야 한다는 단점이 있습니다. 음의 가중치를 가진 간선이 존재한다면 벨만 포드 알고리즘을 통해서 ..
Algorithms/Graph 2021. 9. 11. 08:43

[BOJ 1753] (Dijkstra)최단경로 (C++)

최단경로 (Gold 5) 문제 전체 문제 보기 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 접근법 간선에 가중치가 없는 그래프에서 최단거리는 BFS로 풀 수 있습니다. 하지만 간선에 가중치가 있을 경우 BFS로는 최단 경로를 구할 수 없습니다. 이때는 다익스트라(Dijkstra) 알고리즘을 활용해야 합니다. 다익스트라 알고리즘은 양의 가중치를 가진 경로가 주어졌을 때 최단거리를 구할 수 있는 알고리즘입니다. 시간 복잡도를 살펴보면 BFS는 모든 노드와 간선을 방문하기 때문에 \(..
Algorithms/Graph 2021. 9. 10. 17:16

[프로그래머스](Graph) 순위(C++)

순위(Level 3) 문제 전체 문제 보기 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 접근법 이 문제에서 구해야 하는 것은 순위를 알수 없는 선수의 숫자이다. 문제에서 주어진 예시를 그래프와 표로 나타내면 다음과 같다. 문제의 제한사항을 보면 A선수가 B 선수보다 실력이 좋으면 항상 A선수가 이긴다고 했다. 즉 A선수가 B를 이기고, B선수가 C선수를 이긴다면 A선수는 항상 C 선수를 이긴다는 뜻이다. 이러한 규칙으로 위 그래프에서 추론할 수 있는 경기 결과를 정리해보면 다음과 같을 것이다. 1은 2를 이겼고, 2는 5를 이겼기 때문에 1은 5를 이길 것이다. 4는 2를 이겼고, 2는 5를 이겼기 때문에 4는 ..
Algorithms/Graph 2021. 7. 14. 16:47