[BOJ알고리즘, C++]#14938_서강 그라운드, 최단 경로 알고리즘, 길 다익스트라 알고리즘

2024. 1. 26. 12:14· 문제 풀이/BOJ 문제 풀이
목차
  1. #1. 문제
  2. #2. 풀이
  3. 1. 길 찾기 알고리즘
  4. 2. 다익스트라 알고리즘
  5. 3. 최단 경로 값이 수색 범위 내 있다면, 획득 가능한 아이템 개수를 구하자!
  6. #3. 코드

 

#1. 문제

 

14938번: 서강그라운드

예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을

www.acmicpc.net

 


 

#2. 풀이

 

1. 길 찾기 알고리즘

 

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

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

webddevys.tistory.com

 

[정의] : 최단 경로 알고리즘은 가중치 그래프 내 출발점과 도착점 사이의 경로들 중 가중치의 합이 최소가 되는 경로를 찾는 알고리즘입니다. 최단 경로 알고리즘으로 (1) 다익스트라 알고리즘, (2) 벨만-포드 알고리즘, (3) 플로이드-워셜 알고리즘 등이 있습니다.

 

2. 다익스트라 알고리즘

 

[정의] : 다익스트라 알고리즘은 최단 경로 알고리즘 중 하나로 단일 출발 최단 경로 알고리즘입니다. 다익스트라 알고리즘은 임의의 출발 정점으로부터 다른 모든 노드 사이의 최단 경로를 구하는 데 사용되며, "우선순위 큐" 자료구조를 활용해 구현 가능합니다.

 

3. 최단 경로 값이 수색 범위 내 있다면, 획득 가능한 아이템 개수를 구하자!

 

  1. 먼저, 모든 정점에 대하여 다익스트라를 수행합니다.
  2. 그리고, 도착 정점이 수색 범위 내 존재하는 모든 정점에 대하여 획득 가능한 아이템 개수의 총합을 구합니다.
  3. 마지막으로, 획득 가능한 아이템 개수가 최대가 되는 수를 출력해줍니다.

 


 

#3. 코드

 

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <climits>
using namespace std;

typedef pair<int,int> p;

int n, m, r, maxItems, res;
vector<int> t;
vector<vector<p>> graph;

// 다익스트라 정의
void dijkstra(int start)
{
    vector<bool> visited(n+1, false);
    vector<int> dist(n+1, INT_MAX);
    priority_queue<p, vector<p>, greater<p>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while(!pq.empty())
    {
        int cur_vertex = pq.top().second;
        int cur_weight = pq.top().first;
        pq.pop();
        
        if(visited[cur_vertex])
            continue;
        
        visited[cur_vertex] = true;
        
        for(const auto& edge : graph[cur_vertex])
        {
            int neighbor_vertex = edge.second;
            int neighbor_weight = edge.first;
            
            int new_dist = cur_weight + neighbor_weight;
            if(dist[neighbor_vertex] > new_dist)
            {
                dist[neighbor_vertex] = new_dist;
                pq.push({new_dist, neighbor_vertex});
            }
        }
    }
    // 각 정점들의 최단 거리 비용을 순회하며 수색 범위 내 존재하는 지역들의 아이템 개수의 총합을 구합니다.
    int tmp = 0;
    for(int i=1; i<=n; ++i)
    {
        if(dist[i] <= m)
        {
            tmp += t[i];
        }
    }
    // 구할 수 있는 아이템 최대 개수 갱신
    res = max(res, tmp);
}
    
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> r;
       
    t.resize(n+1);
    graph.resize(n+1);
    
    for(int i=1; i<=n; ++i)
        cin >> t[i];
    
    while(r--)
    {
        int a, b, c;
        
        cin >> a >> b >> c;
        
        graph[a].push_back({c, b});
        graph[b].push_back({c, a});
    }
    
    // 다익스트라 수행
    for(int i=1; i<=n; ++i)
        dijkstra(i);
    
    // 정답 출력
    cout << res;
    
    return 0;
}

 


 

 

 

저작자표시 (새창열림)

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

[BOJ알고리즘, C++]#2665_미로 만들기, 최단 경로 알고리즘, 다익스트라 알고리즘  (1) 2024.01.26
[BOJ알고리즘, C++]#2458, 키 순서, 최단 경로 알고리즘, 플로이드-워셜 알고리즘, 플로이드 알고리즘  (0) 2024.01.26
[BOJ알고리즘, C++]#4485_녹색 옷 입은 애가 젤다지?, 최단 경로 알고리즘, 길 찾기 알고리즘, 다익스트라  (1) 2024.01.10
[BOJ알고리즘, C++]#18352_특정 거리의 도시 찾기, 최단 경로 알고리즘, BFS  (0) 2024.01.10
[BOJ알고리즘, C++]#1261_알고스팟, 최단 경로 알고리즘, 다익스트라 알고리즘  (0) 2024.01.10
  1. #1. 문제
  2. #2. 풀이
  3. 1. 길 찾기 알고리즘
  4. 2. 다익스트라 알고리즘
  5. 3. 최단 경로 값이 수색 범위 내 있다면, 획득 가능한 아이템 개수를 구하자!
  6. #3. 코드
'문제 풀이/BOJ 문제 풀이' 카테고리의 다른 글
  • [BOJ알고리즘, C++]#2665_미로 만들기, 최단 경로 알고리즘, 다익스트라 알고리즘
  • [BOJ알고리즘, C++]#2458, 키 순서, 최단 경로 알고리즘, 플로이드-워셜 알고리즘, 플로이드 알고리즘
  • [BOJ알고리즘, C++]#4485_녹색 옷 입은 애가 젤다지?, 최단 경로 알고리즘, 길 찾기 알고리즘, 다익스트라
  • [BOJ알고리즘, C++]#18352_특정 거리의 도시 찾기, 최단 경로 알고리즘, BFS
Hardii2
Hardii2
개발 블로그Hardii2 님의 블로그입니다.
Hardii2
개발 블로그
Hardii2
전체
오늘
어제
  • 분류 전체보기
    • 알고리즘
    • 웹 개발
      • Node.js
      • React
    • 게임개발
      • DirectX12
      • 관련 지식
      • Unreal C++
      • Unreal 블루프린트
    • 언어
      • Effective C++
      • Basic C++
      • 디자인 패턴
      • 자료구조
      • 기술 질문
    • 문제 풀이
      • BOJ 문제 풀이
      • Programmers 문제 풀이
      • geeksForgeeks 문제 풀이
    • 수학
      • 확률과 통계
      • 게임수학
    • 개인프로젝트
    • 그룹프로젝트
      • PM
      • Dev
    • Github

블로그 메뉴

  • 홈
  • 글쓰기

공지사항

인기 글

태그

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

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
Hardii2
[BOJ알고리즘, C++]#14938_서강 그라운드, 최단 경로 알고리즘, 길 다익스트라 알고리즘
상단으로

티스토리툴바

개인정보

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

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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