[Python][C++] 1238번 파티

문제

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

 

 

 

 

 

 

코드

1. Python

import sys
import heapq

input = sys.stdin.readline  # 빠른 입력을 위해 sys.stdin.readline 사용

# n: 마을의 개수, m: 도로의 개수, x: 파티가 열리는 마을 번호
n, m, x = map(int, input().split())

# 그래프 초기화 (1번 마을부터 시작하므로 n+1 크기)
graph = [[] for _ in range(n + 1)]

# m개의 도로 입력 처리
for _ in range(m):
    start, end, w = map(int, input().split())  # start: 출발 마을, end: 도착 마을, w: 도로의 거리
    graph[start].append([end, w])  # 출발 마을에서 도착 마을로 가는 도로와 그 거리를 저장

# 다익스트라 알고리즘 구현
def dijkstra(v):
    # 각 마을까지의 최소 거리를 기록할 리스트, 초기에는 매우 큰 값으로 설정
    visited = [1e9] * (n + 1)
    visited[v] = 0  # 시작 마을에서 시작 마을로 가는 거리는 0
    heap = [[0, v]]  # 힙에 [거리, 시작 마을]을 넣어 시작

    # 힙이 빌 때까지 반복
    while heap:
        w, v = heapq.heappop(heap)  # 힙에서 현재까지의 거리 w와 현재 마을 v를 꺼냄

        if w > visited[v]:  # 이미 방문한 마을이면 넘어감
            continue

        # 현재 마을에서 이동할 수 있는 모든 경로에 대해 처리
        for nv, nw in graph[v]:
            tmp = w + nw  # 현재 거리 w에 다음 마을까지의 거리 nw를 더함
            if tmp < visited[nv]:  # 더 짧은 경로가 있다면 업데이트
                visited[nv] = tmp
                heapq.heappush(heap, [tmp, nv])  # 새로운 경로를 힙에 추가

    return visited  # 시작 마을에서 다른 마을까지의 최단 거리를 반환

# 파티에서 집까지 왕복하는 데 걸리는 시간이 가장 긴 학생의 왕복 시간 구하기
ans = 0
dij1 = dijkstra(x)  # x 마을에서 모든 마을까지 가는 최단 거리 (파티에서 집으로 가는 거리)
for i in range(1, n + 1):
    if i == x:  # 자기 자신으로의 왕복은 계산할 필요가 없으므로 패스
        continue

    dij2 = dijkstra(i)  # i 마을에서 x 마을까지 가는 최단 거리 (집에서 파티로 가는 거리)
    ans = max(ans, dij2[x] + dij1[i])  # 가장 오래 걸리는 왕복 시간을 계산

# 최종적으로 가장 긴 왕복 시간을 출력
print(ans)

 

2.C++

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>

using namespace std;

// 다익스트라 알고리즘을 사용해 시작 노드 v에서 목표 노드 target까지의 최단 경로를 구함
int dijkstra(int v, const int target, const int n, const vector<vector<pair<int, int>>>& graph) {
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;  // 최소 힙을 위한 우선순위 큐
	vector<int> visited(n+1);  // 방문 여부를 기록하는 배열
	int w = 0;

	pq.push(make_pair(0, v));  // 시작 노드를 큐에 삽입 (거리, 노드 번호)

	while (!pq.empty()) {
		tie(w, v) = pq.top();  // 현재 노드와 그까지의 거리
		pq.pop();

		// 목표 노드에 도달하면 그때의 거리를 반환
		if (v == target)
			return w;

		visited[v] = 1;  // 현재 노드를 방문 처리

		// 현재 노드와 연결된 모든 노드를 탐색
		for (auto g : graph[v]) {
			int nv = g.first;  // 다음 노드
			int nw = g.second;  // 다음 노드까지의 가중치

			// 방문하지 않은 노드에 대해서만 큐에 추가
			if (!visited[nv]) {
				pq.push(make_pair(nw + w, nv));  // 누적된 거리를 큐에 삽입
			}
		}
	}

	return -1;  // 목표 노드에 도달할 수 없는 경우 (여기서는 없을 것으로 가정)
}

int main() {
	int n, m, x;
	cin >> n >> m >> x;  // n: 노드 수, m: 간선 수, x: 목적지 노드

	vector<vector<pair<int, int>>> graph(n+1);  // 그래프 저장 (인접 리스트)

	// 그래프 입력
	while (m--) {
		int u, v, w;
		cin >> u >> v >> w;  // u에서 v로 가는 가중치 w의 간선 입력
		graph[u].push_back(make_pair(v, w));
	}

	vector<int> times(n+1);  // 각 노드에서 출발해 돌아오는 시간을 저장할 벡터
	
	// 각 노드에서 x로 갔다가 돌아오는 데 걸리는 시간 계산
	for (int i = 1; i <= n; i++) {
		int time = 0;
		time += dijkstra(i, x, n, graph);  // i에서 x까지 가는 최단 경로
		time += dijkstra(x, i, n, graph);  // x에서 i로 돌아오는 최단 경로
		times[i] = time;  // 해당 노드의 왕복 시간 저장
	}

	// 가장 오래 걸리는 왕복 시간 출력
	cout << *max_element(times.begin(), times.end());

	return 0;
}

 

 

 

풀이

 

1. 문제 분석:
   • 각 마을 간의 도로가 주어지고, 도로는 방향성(단방향)을 가진다.
   • 주어진 특정 마을(파티가 열리는 마을)로 갔다가 다시 원래 마을로 돌아오는 데 걸리는 시간을 구해야 한다.
   • 각 학생이 자기 마을에서 파티가 열리는 마을까지 갔다가 돌아오는 데 걸리는 시간 중 최댓값을 구하는 것이 목표이다.
2. 다익스트라 알고리즘:
   • 다익스트라 알고리즘을 사용하여, 한 노드에서 다른 모든 노드로의 최단 경로를 구할 수 있다.
   • 두 번의 다익스트라 알고리즘을 사용하여 문제를 해결할 수 있다:
     1. 각 마을에서 파티가 열리는 마을까지의 최단 경로를 구한다.
     2. 파티가 열리는 마을에서 각 마을로 돌아가는 최단 경로를 구한다.
3. 출력:
   • 각 학생의 왕복 경로 시간을 계산하고, 그 중 가장 큰 값을 출력한다.