[알고리즘 문제 풀기] 파티(1238)

1. 문제 풀이 아이디어

• 방향 그래프이므로 다익스트라를 두 번 수행해 i → X, X → i 각각의 최단 경로를 구해 문제를 해결할 수 있다.

2. 나의 정답 코드

using System.Collections.Generic;

class PriorityQueue<T>
{
	private List<Tuple<T, int>> _heap = new List<Tuple<T, int>>();
	private void Swap(int i, int j)
	{
		var temp = _heap[i];
		_heap[i] = _heap[j];
		_heap[j] = temp;
	}
	private void HeapifyUp(int index)
	{
		while (index > 0)
		{
			int parent = (index - 1) / 2;
			if (_heap[index].Item2 >= _heap[parent].Item2) break;
			Swap(index, parent);
			index = parent;
		}
	}
	private void HeapifyDown(int index)
	{
		int last = _heap.Count - 1;
		while (true)
		{
			int left = 2 * index + 1;
			int right = 2 * index + 2;
			int smallest = index;
			if (left <= last && _heap[left].Item2 < _heap[smallest].Item2)
				smallest = left;
			if (right <= last && _heap[right].Item2 < _heap[smallest].Item2)
				smallest = right;
			if (smallest == index) break;
			Swap(index, smallest);
			index = smallest;
		}
	}
	public void Enqueue(T item, int priority)
	{
		_heap.Add(Tuple.Create(item, priority));
		HeapifyUp(_heap.Count - 1);
	}
	public T Dequeue()
	{
		var root = _heap[0].Item1;
		_heap[0] = _heap[_heap.Count - 1];
		_heap.RemoveAt(_heap.Count - 1);
		HeapifyDown(0);
		return root;
	}
	public int PeekPriority()
	{
		return _heap[0].Item2;
	}
	public int Count => _heap.Count;
}

class Program
{
	static void Main(string[] args)
	{
		using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
		using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
		{
			string[] split = sr.ReadLine().Split();
			int n = int.Parse(split[0]);
			int m = int.Parse(split[1]);
			int x = int.Parse(split[2]);
			Dictionary<int, int>[] dict = new Dictionary<int, int>[n + 1];
			for (int i = 1; i <= n; i++) dict[i] = new Dictionary<int, int>();
			for (int i = 0; i < m; i++)
			{
				split = sr.ReadLine().Split();
				int a = int.Parse(split[0]);
				int b = int.Parse(split[1]);
				int d = int.Parse(split[2]);
				dict[a].Add(b, d);
			}
			int result = 0;
			for (int i = 1; i <= n; i++)
			{
				result = Math.Max(result, Dist(i, x) + Dist(x, i));
			}
			sw.WriteLine(result);

			int Dist(int a, int b)
			{
				if(a == b) return 0;
				PriorityQueue<int> que = new PriorityQueue<int>();
				bool[] visited = new bool[n + 1];
				foreach (var i in dict[a])
				{
					que.Enqueue(i.Key, i.Value);
				}
				while (que.Count > 0)
				{
					int dist = que.PeekPriority();
					int cur = que.Dequeue();
					if (cur == b) return dist;
					if (visited[cur]) continue;
					visited[cur] = true;
					foreach (var next in dict[cur])
					{
                        if (visited[next.Key]) continue;
						que.Enqueue(next.Key, dist + next.Value);
					}
				}
				return -1;
			}
		}
	}
}

3. 정리

• dict[a][b] = d로 간선 정보를 방향 그래프로 저장한다.

• 각 정점 i에서 X까지의 최단 거리 Dist(i, x)를 구하고

• X에서 다시 i로 돌아가는 최단 거리 Dist(x, i)도 구한다.

• 왕복 거리는 두 거리의 합이며, 이 중 최대 값을 구한다.

• Dist 함수는 다익스트라 방식으로, 우선순위 큐를 활용해 최단 경로를 구한다.

• 방문 배열 visited를 사용해 중복 방문을 방지하며, 큐에 인접 노드들을 계속 삽입하여 탐색을 진행한다.