[알고리즘 문제 풀기] 도시 분할 계획(1647)

1. 문제 풀이 아이디어

• 최소 스패닝 트리(MST, Minimum Spanning Tree)를 활용하여 문제를 해결할 수 있다.

• 1번은 Prim 알고리즘을 사용하여 해결하였고 2번은 Kruskal 알고리즘을 사용하여 해결하였다.

2. 나의 정답 코드 1

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())) {
			int[] input = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
			int n = input[0];
			int m = input[1];
			List<int[]>[] list = new List<int[]>[n + 1];
			for (int i = 1; i <= n; i++) list[i] = new List<int[]>();
			for (int i = 0; i < m; i++) {
				input = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
				int a = input[0];
				int b = input[1];
				int d = input[2];
				list[a].Add(new int[] { b, d });
				list[b].Add(new int[] { a, d });
			}
			bool[] visited = new bool[n + 1];

			PriorityQueue<int> pq = new PriorityQueue<int>();
			pq.Enqueue(1, 0);
			int count = 0;
			int result = 0;
			int max = 0;
			while (pq.Count > 0 && count < n) {
				int dist = pq.PeekPriority();
				int cur = pq.Dequeue();
				if (visited[cur]) continue;
				visited[cur] = true;
				result += dist;
				max = Math.Max(dist, max);
				count++;
				foreach (int[] next in list[cur]) {
					if (visited[next[0]]) continue;
					pq.Enqueue(next[0], next[1]);
				}
			}
			sw.WriteLine(result - max);
		}
	}
}

3. 정리 1

• n과 m을 읽어 인접 리스트 형태로 간선 정보를 저장한다.

• visited 배열을 초기화하고 시작 노드를 가중치 0으로 우선순위 큐에 삽입한다.

• 큐에서 최소 가중치 간선을 꺼내 해당 노드가 미방문이면 방문 처리하고 가중치를 누적하며 최대값을 갱신한다.

• 꺼낸 노드의 모든 인접 간선을 확인해 미방문 노드를 우선순위 큐에 삽입한다.

• 모든 노드를 연결한 뒤 누적 가중치에서 기록된 최대값을 제외한 값을 출력한다.

4. 나의 정답 코드 2

class Line {
    public int a, b, d;
    public Line(int _a, int _b, int _d) { a = _a; b = _b; d = _d; }
}
class Program {
    static void Main(string[] args) {
        using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
            using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput())) {
            int[] input = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
            int n = input[0];
            int m = input[1];

            List<Line> lines = new List<Line>();
            for (int i = 0; i < m; i++) {
                input = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
                lines.Add(new Line(input[0], input[1], input[2]));
            }
            lines.Sort((l1, l2) => l1.d.CompareTo(l2.d));

            int[] p = new int[n + 1];
            for (int i = 1; i <= n; i++) p[i] = i;
            int result = 0;
            int count = 0;
            int max = 0;
            foreach (Line line in lines) {
                if (Union(line.a, line.b)) {
                    result += line.d;
                    max = Math.Max(line.d, max);
                    count++;
                    if (count == n - 1) break;
                }
            }
            sw.WriteLine(result - max);

            int Find(int x) {
                if (p[x] == x) return x;
                return p[x] = Find(p[x]);
            }
            bool Union(int x, int y) {
                x = Find(x);
                y = Find(y);
                if (x == y) return false;
                p[x] = y;
                return true;
            }
        }
    }
}

5. 정리 2

• n과 m을 읽어 Line 객체 리스트에 각 간선을 저장하고 가중치 오름차순으로 정렬한다.

• 부모 배열을 초기화해 Union‑Find 함수를 준비한다.

• 정렬된 간선을 순차적으로 검사해 서로 다른 집합의 두 정점을 연결하면 가중치를 누적하고 최대값을 갱신한다.

• 연결된 간선 수가 n‑1이 되면 반복을 종료한다.

• 누적 가중치에서 기록된 최대값을 제외한 값을 출력한다.