백준 17270// 연예인은 힘들어//다익스트라 알고리즘 (Dijkstra's Algorithm)//

cote/Challenge

by geminanolja 2025. 1. 20. 00:00

https://www.acmicpc.net/problem/17270

지헌과 성하의 출발지로부터 새로운 약속 장소를 선정:약속 장소 후보는 지헌(J)과 성하(S)의 출발지가 아닌 위치여야 한다.약속 장소까지의 **최단 거리 합(지헌 → 약속 장소 + 성하 → 약속 장소)**이 최소인 위치를 선택한다.최단 거리 합이 같다면:지헌이 성하보다 늦게 도착하면 안 된다.지헌과 성하가 동시에 도착하거나, 지헌이 더 빨리 도착해야 한다.최종 조건을 만족하는 장소가 여러 개라면:지헌으로부터 가장 가까운 곳을 선택.그것도 같다면, 번호가 가장 작은 장소를 선택.

입력
첫 줄: 약속 장소 후보의 수 VVV와 길의 수 MMM.2≤V≤1002 \leq V \leq 1002≤V≤100, 1≤M≤1,0001 \leq M \leq 1,0001≤M≤1,000.다음 MMM개의 줄: a,b,ca, b, ca,b,c가 주어짐:aaa와 bbb는 길의 양 끝, ccc는 이동 시간.길은 양방향.마지막 줄: 지헌의 위치 JJJ, 성하의 위치 SSS.

출력
조건을 만족하는 최적 약속 장소를 출력.조건을 만족하는 장소가 없다면 **-1**을 출력.

알고리즘

1. 다익스트라 알고리즘 (Dijkstra's Algorithm)

목적:

그래프에서 특정 시작 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘.

주요 특징:

가중치가 있는 그래프에서 동작하며, 간선의 가중치는 음수가 아니어야 한다.
우선순위 큐를 사용해 효율적으로 최단 경로를 계산한다.
시간 복잡도: O(Elog⁡V)O(E \log V)
- EE: 간선의 수
- VV: 노드의 수

2. 코드에서 사용된 다익스트라 알고리즘

동작:

특정 출발 노드(st)에서 시작하여, 다른 모든 노드까지의 최단 거리를 계산.
우선순위 큐를 이용하여 현재까지 계산된 최단 거리 중 가장 작은 노드를 탐색.
선택된 노드의 인접 노드들을 확인하며, 더 짧은 경로가 발견되면 갱신.
각 노드에 대해 최단 거리가 계산되면 종료.

코드 구현 부분:

void Dijstra(int st) {
    reset_distance();                // 거리 배열 초기화
    Distance[st] = 0;                // 출발지까지의 거리는 0
    q.push({-Distance[st], st});     // 우선순위 큐에 초기값 삽입

    while (!q.empty()) {
        int x = q.top().S;           // 현재 노드
        int cost = -q.top().F;       // 현재 노드까지의 거리
        q.pop();

        if (Distance[x] < cost) continue; // 이미 더 짧은 거리가 있으면 스킵

        // 현재 노드의 모든 인접 노드 탐색
        for (int i = 0; i < connect[x].size(); i++) {
            int xx = connect[x][i].F;    // 다음 노드
            int n_cost = cost + connect[x][i].S; // 다음 노드까지의 거리

            // 더 짧은 거리를 발견하면 업데이트
            if (Distance[xx] > n_cost) {
                Distance[xx] = n_cost;
                q.push({-Distance[xx], xx}); // 우선순위 큐에 삽입
            }
        }
    }
}

작동 방식:

reset_distance()를 호출해 모든 노드의 거리를 무한대(INF)로 초기화.
출발 노드의 거리를 0으로 설정하고 우선순위 큐에 삽입.
큐에서 최단 거리가 가장 짧은 노드를 추출.
추출된 노드의 인접 노드들을 확인하고, 더 짧은 경로가 발견되면 거리를 업데이트.
모든 노드에 대해 반복.

3. 조건 탐색 및 최적의 약속 장소 찾기

조건 확인:

지헌(J)과 성하(S)의 출발지가 아닌 노드만 고려:
```
if (i == J || i == S) continue;
```

지헌과 성하의 이동 거리 합이 최소여야 함:

JS_distance = min(JS_distance, J_Distance[i] + S_Distance[i]);

지헌이 성하보다 늦게 도착해서는 안 됨:
```
if (J_Distance[i] > S_Distance[i]) continue;
```

지헌에게 더 가까운 장소를 선택:

if (J_dis >= J_Distance[i]) {
    J_dis = J_Distance[i];
    Point = i;
}

4. 이 코드를 통해 해결한 문제

다익스트라 알고리즘을 두 번 실행하여, 지헌(J)과 성하(S)의 출발점에서 각 노드까지의 최단 거리를 계산.
계산된 거리 정보를 바탕으로 조건을 검토하며, 최적의 약속 장소를 선택.

5. 시간 복잡도 분석

다익스트라 알고리즘:

O((V+E)log⁡V)O((V + E) \log V): 각 노드와 간선을 처리하며 우선순위 큐를 사용.
- VV: 노드 수
- EE: 간선 수
이 코드는 다익스트라 알고리즘을 두 번 실행하므로, 전체 시간 복잡도는 O((V+E)log⁡V)O((V + E) \log V)에 두 배.

탐색 및 조건 확인:

노드 수 VV에 대해 선형 탐색을 수행하므로 O(V)O(V).

최종 시간 복잡도:

O((V+E)log⁡V)O((V + E) \log V).

6. 사용된 알고리즘

다익스트라 알고리즘:
- 특정 노드에서 다른 모든 노드까지의 최단 거리 계산.
조건 탐색:
- 다익스트라로 계산된 거리 정보를 기반으로 조건을 검토하며 최적의 노드를 선택.

구현

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#define INF 2100000000 // 무한대를 나타내는 값
#define F first       // pair에서 first를 F로 줄여 사용
#define S second      // pair에서 second를 S로 줄여 사용

using namespace std;

int N, M;                      // N: 노드 개수, M: 간선 개수
int J, S;                      // J: 지헌의 출발지, S: 성하의 출발지
vector<pair<int, int>> connect[101]; // 그래프의 연결 정보를 저장 (인접 리스트)
priority_queue<pair<int, int>, vector<pair<int, int>>> q; // 다익스트라를 위한 우선순위 큐
int Distance[101];             // 특정 출발지에서 각 노드까지의 최단 거리
int J_Distance[101];           // J -> X 최단 거리 저장
int S_Distance[101];           // S -> X 최단 거리 저장

// Distance 배열을 INF로 초기화 (새로운 다익스트라 실행을 준비)
void reset_distance() {
    for (int i = 1; i <= N; i++) Distance[i] = INF;
}

// 다익스트라 알고리즘: 특정 출발지(st)에서 각 노드까지의 최단 거리 계산
void Dijstra(int st) {
    reset_distance();                // 거리 배열 초기화
    Distance[st] = 0;                // 출발지까지의 거리는 0
    q.push({-Distance[st], st});     // 우선순위 큐에 초기값 삽입

    while (!q.empty()) {
        int x = q.top().S;           // 현재 노드
        int cost = -q.top().F;       // 현재 노드까지의 거리
        q.pop();

        if (Distance[x] < cost) continue; // 이미 더 짧은 거리가 있으면 스킵

        // 현재 노드의 모든 인접 노드 탐색
        for (int i = 0; i < connect[x].size(); i++) {
            int xx = connect[x][i].F;    // 다음 노드
            int n_cost = cost + connect[x][i].S; // 다음 노드까지의 거리

            // 더 짧은 거리를 발견하면 업데이트
            if (Distance[xx] > n_cost) {
                Distance[xx] = n_cost;
                q.push({-Distance[xx], xx}); // 우선순위 큐에 삽입
            }
        }
    }
}

// 약속 장소를 찾는 메인 로직
void solve() {
    int JS_distance = INF; // 지헌과 성하의 거리 합의 최소값
    int Point = -1;        // 최적의 약속 장소
    int J_dis = INF;       // 지헌으로부터 가장 가까운 거리

    // 지헌 -> 모든 노드까지 최단 거리 계산
    Dijstra(J);
    for (int i = 1; i <= N; i++) {
        J_Distance[i] = Distance[i]; // 지헌 기준 거리 저장
    }

    // 성하 -> 모든 노드까지 최단 거리 계산
    Dijstra(S);
    for (int i = 1; i <= N; i++) {
        S_Distance[i] = Distance[i]; // 성하 기준 거리 저장
    }

    // 약속 장소 후보 탐색
    for (int i = 1; i <= N; i++) 
    {
        if (i == J || i == S) continue; // 조건 1: 지헌과 성하의 출발지는 제외
        JS_distance = min(JS_distance, J_Distance[i] + S_Distance[i]); // 거리 합의 최소값 계산
    }

    // 조건에 맞는 최적의 약속 장소 선택
    for (int i = N; i >= 1; i--) 
    { // 번호가 큰 장소부터 탐색
        if (i == J || i == S) continue; // 조건 1: 지헌과 성하의 출발지는 제외
        if (JS_distance != J_Distance[i] + S_Distance[i]) continue; // 거리 합이 최소값이 아니면 제외
        if (J_Distance[i] > S_Distance[i]) continue; // 조건 3: 지헌이 성하보다 늦게 도착하면 안 됨
        if (J_dis >= J_Distance[i]) { // 지헌으로부터 가까운 장소를 선택
            J_dis = J_Distance[i];
            Point = i; // 최적의 약속 장소 업데이트
        }
    }

    cout << Point; // 결과 출력
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M; // 노드 수와 간선 수 입력
    for (int i = 1; i <= M; i++) 
    {
        int x, y, cost;
        cin >> x >> y >> cost; // 간선 정보 입력
        connect[x].push_back({y, cost}); // 양방향 간선 저장
        connect[y].push_back({x, cost});
    }
    cin >> J >> S; // 지헌과 성하의 출발지 입력
    solve();       // 약속 장소 계산
    return 0;
}

예제 입력

노드 수: 8, 간선 수: 10  
1 2 2  
2 6 3  
2 3 4  
3 7 2  
7 4 5  
5 6 2  
5 7 1  
7 8 2  
5 8 2  
3 6 3  
지헌의 출발지: 3, 성하의 출발지: 6

그래프 구성

간선 데이터를 바탕으로 connect 배열이 다음과 같이 구성됩니다:

connect[1] = { {2, 2} };
connect[2] = { {1, 2}, {6, 3}, {3, 4} };
connect[3] = { {2, 4}, {7, 2}, {6, 3} };
connect[4] = { {7, 5} };
connect[5] = { {6, 2}, {7, 1}, {8, 2} };
connect[6] = { {2, 3}, {3, 3}, {5, 2} };
connect[7] = { {3, 2}, {4, 5}, {5, 1}, {8, 2} };
connect[8] = { {7, 2}, {5, 2} };

다익스트라 알고리즘 계산 과정

1. 지헌(3번) 출발 → 모든 노드까지 거리 계산

Dijkstra(3) 실행:

초기 상태:

Distance: [INF, INF, INF, 0, INF, INF, INF, INF, INF]
우선순위 큐: { (0, 3) }

반복 1: 현재 노드 3

connect[3] 탐색:
- 2번: 거리 4
- 7번: 거리 2
- 6번: 거리 3

거리 배열 업데이트:

Distance: [INF, INF, 4, 0, INF, 3, 2, INF, INF]
우선순위 큐: { (2, 7), (4, 2), (3, 6) }

반복 2: 현재 노드 7

connect[7] 탐색:
- 3번: 이미 방문, 스킵
- 4번: 거리 7
- 5번: 거리 3
- 8번: 거리 4

거리 배열 업데이트:

Distance: [INF, INF, 4, 0, 7, 3, 2, 4, INF]
우선순위 큐: { (3, 5), (4, 2), (3, 6), (7, 4), (4, 8) }

반복 3~완료: 큐가 빌 때까지 반복

최종 거리 배열:

Distance (지헌 기준): [INF, INF, 4, 0, 7, 3, 2, 4, 4]

2. 성하(6번) 출발 → 모든 노드까지 거리 계산

Dijkstra(6) 실행 결과:

최종 거리 배열:

Distance (성하 기준): [INF, INF, 3, 3, 7, 2, 0, 3, 4]

1단계: 약속 장소 후보 탐색

for (int i = 1; i <= N; i++) {
    if (i == J || i == S) continue; // 지헌(3번), 성하(6번) 제외
    JS_distance = min(JS_distance, J_Distance[i] + S_Distance[i]); // 최소 거리 합 계산
}

각 장소에서 거리 합 계산:
- 1번: INF (성하 도달 불가)
- 2번: J_Distance[2] + S_Distance[2] = 4 + 3 = 7
- 3번: 제외 (지헌의 출발지)
- 4번: J_Distance[4] + S_Distance[4] = 7 + 7 = 14
- 5번: J_Distance[5] + S_Distance[5] = 3 + 2 = 5
- 6번: 제외 (성하의 출발지)
- 7번: J_Distance[7] + S_Distance[7] = 2 + 3 = 5
- 8번: J_Distance[8] + S_Distance[8] = 4 + 4 = 8
최소 거리 합: 5

2단계: 조건에 맞는 최적의 약속 장소 선택

for (int i = N; i >= 1; i--) {
    if (i == J || i == S) continue; // 조건 1: 지헌과 성하의 출발지 제외
    if (JS_distance != J_Distance[i] + S_Distance[i]) continue; // 최소 거리 합 아닌 경우 제외
    if (J_Distance[i] > S_Distance[i]) continue; // 조건 3: 지헌이 성하보다 늦으면 제외
    if (J_dis >= J_Distance[i]) { // 지헌으로부터 가까운 장소 선택
        J_dis = J_Distance[i];
        Point = i; // 최적의 약속 장소 업데이트
    }
}

조건을 만족하는 장소들:
- 5번: J_Distance[5] = 3, S_Distance[5] = 2 → 조건 3 만족
- 7번: J_Distance[7] = 2, S_Distance[7] = 3 → 조건 3 만족
지헌으로부터 가까운 장소:
- 7번 (거리: 2)
- 최적 약속 장소: 7번

출력

1. 주요 목적

이 코드는 다익스트라 알고리즘을 활용하여, 문제에서 제시된 조건을 만족하는 최적의 약속 장소를 찾는 프로그램입니다.
조건:
1. 약속 장소는 지헌(J)과 성하(S)의 출발지가 될 수 없다.
2. 지헌과 성하가 약속 장소까지 이동하는 거리 합이 최소여야 한다.
3. 지헌이 성하보다 늦게 도착해서는 안 된다.
4. 조건을 만족하는 약속 장소가 여러 개라면, 지헌에게 가장 가까운 장소를 선택한다.
5. 지헌에게도 같은 거리라면, 번호가 큰 장소를 선택한다.

2. 코드 구조

2.1. 변수 초기화

int N, M;
int J, S;
vector<pair<int, int>> connect[101];
priority_queue<pair<int, int>, vector<pair<int, int>>> q;
int Distance[101];
int J_Distance[101]; // 지헌 -> 다른 노드 거리
int S_Distance[101]; // 성하 -> 다른 노드 거리

N: 노드 수 (약속 장소 수)
M: 간선 수 (도로 정보)
J: 지헌의 출발 위치
S: 성하의 출발 위치
connect: 각 노드 간 연결 정보를 저장 (인접 리스트).
Distance: 다익스트라 알고리즘 실행 중 현재 노드까지의 최단 거리.
J_Distance와 S_Distance: 각각 지헌과 성하가 각 노드까지 이동하는 최단 거리.

2.2. reset_distance 함수

void reset_distance() {
    for (int i = 1; i <= N; i++) Distance[i] = INF;
}

Distance 배열을 INF로 초기화하여 새로운 다익스트라 실행 시 사용 가능하도록 준비.

2.3. Dijstra 함수

void Dijstra(int st) {
    reset_distance();
    Distance[st] = 0;
    q.push({-Distance[st], st});
    while (!q.empty()) {
        int x = q.top().S;
        int cost = -q.top().F;
        q.pop();
        if (Distance[x] < cost) continue;
        for (int i = 0; i < connect[x].size(); i++) {
            int xx = connect[x][i].F;
            int n_cost = cost + connect[x][i].S;
            if (Distance[xx] > n_cost) {
                Distance[xx] = n_cost;
                q.push({-Distance[xx], xx});
            }
        }
    }
}

목적:
- 특정 시작 노드(st)에서 다른 모든 노드까지의 최단 거리를 계산.
- 다익스트라 알고리즘을 구현.
작동 원리:
1. Distance[st] = 0으로 시작 노드의 거리를 초기화.
2. 우선순위 큐(priority_queue)를 사용해 현재 최단 거리 노드를 선택.
3. 선택된 노드의 이웃 노드를 탐색하며 최단 거리를 갱신.
4. Distance 배열에 계산된 최단 거리 저장.

2.4. solve 함수

void solve() {
    int JS_distance = INF; // 지헌과 성하의 최소 거리 합
    int Point = -1;        // 약속 장소
    int J_dis = INF;       // 지헌으로부터의 최소 거리

    // 1. 지헌 -> 모든 노드 최단 거리 계산
    Dijstra(J);
    for (int i = 1; i <= N; i++) {
        J_Distance[i] = Distance[i];
    }

    // 2. 성하 -> 모든 노드 최단 거리 계산
    Dijstra(S);
    for (int i = 1; i <= N; i++) {
        S_Distance[i] = Distance[i];
    }

    // 3. 모든 노드에 대해 조건을 만족하는지 검사
    for (int i = 1; i <= N; i++) {
        if (i == J || i == S) continue; // 조건 1: 지헌과 성하의 출발지는 제외
        JS_distance = min(JS_distance, J_Distance[i] + S_Distance[i]); // 최소 거리 합 갱신
    }

    // 4. 최적의 약속 장소 선택
    for (int i = N; i >= 1; i--) { // 번호가 큰 장소부터 검사
        if (i == J || i == S) continue;
        if (JS_distance != J_Distance[i] + S_Distance[i]) continue;
        if (J_Distance[i] > S_Distance[i]) continue; // 조건 3: 지헌이 성하보다 늦게 도착하면 안 됨
        if (J_dis >= J_Distance[i]) {
            J_dis = J_Distance[i];
            Point = i;
        }
    }

    // 5. 결과 출력
    cout << Point;
}

2.5. main 함수

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for (int i = 1; i <= M; i++) {
        int x, y, cost;
        cin >> x >> y >> cost;
        connect[x].push_back({y, cost});
        connect[y].push_back({x, cost});
    }
    cin >> J >> S;
    solve();
    return 0;
}

작동 방식:
1. 입력 데이터를 읽어와 그래프(connect)를 구성.
2. solve 함수를 호출하여 최적의 약속 장소를 계산.

3. 코드의 핵심 로직

다익스트라 알고리즘을 두 번 실행:
- 지헌(J)의 출발점에서 최단 거리 계산.
- 성하(S)의 출발점에서 최단 거리 계산.
각 노드에 대해 조건 검토:
- 지헌과 성하의 출발지가 아니어야 함.
- 지헌과 성하의 이동 거리 합이 최소여야 함.
- 지헌이 성하보다 늦게 도착할 수 없음.
- 조건을 만족하는 장소 중 지헌에게 가장 가까운 장소를 선택.
결과 출력:
- 조건을 만족하는 약속 장소가 없으면 -1 출력.
- 그렇지 않으면 선택된 약속 장소 출력.

4. 장점

다익스트라 알고리즘으로 최단 거리 계산을 효율적으로 수행.
조건을 철저히 검토하여 최적의 약속 장소를 정확히 선택.

5. 예제 실행

입력

출력

이 코드는 최적의 약속 장소를 정확히 찾을 수 있도록 설계되었습니다. 추가 질문이 있다면 언제든 알려주세요! 😊

'cote > Challenge' 카테고리의 다른 글

Programmers 64064 불량 사용자 (0)	2025.02.11
Programmers 양과 늑대 (0)	2025.01.22
백준 17825 주사위 윷놀이 (0)	2025.01.21
항해//프로그래머스 60060// 가사 검색/c++// (3)	2025.01.15
항해 99 //백준 11657 //타임머신//벨만 포드(Bellamn- Ford) 알고리즘 (0)	2025.01.13

geminanolja 님의 블로그

고정 헤더 영역

메뉴 레이어

메뉴 리스트

검색 레이어

검색 영역

상세 컨텐츠

본문 제목

본문