BOJ - 14594번 동방 프로젝트 (Small)

문제 출처: https://www.acmicpc.net/problem/14594

문제 난이도

Silver 3

문제 접근법

벽이 x번 방부터 y번 방까지 뚫린다면 그 방 전체가 한 방이 되는 거니깐 집합이 된다.
그래서 Union&Find 알고리즘이 생갔났다. N은 100까지라서 그냥 알고리즘 짜도 통과할 것 같은데 큰 수일 때를 염두하고 짜봤다.

괜히 더 어렵게 짠거 같다.

통과 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>


using namespace std;


int dp[101];

int Find(int v) {
	if(dp[v] == v) return v;
	else return dp[v] = Find(dp[v]);
}

void Union(int start, int end) {
	for (int i = start; i < end; i++) {
		int a = Find(i);
		int b = Find(i + 1);
		if (a != b) {
			dp[b] = a;
		}
	}
}

int main() {
	int N, M;
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		dp[i] = i;
	}
    	vector<pair<int,int>> tmp;
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		tmp.push_back({a,b});
	}
    	sort(tmp.begin(), tmp.end());
    	for(int i=0; i<tmp.size(); i++){
        	Union(tmp[i].first, tmp[i].second);
    	}
	int cnt = 0;
	int res = 0;
	for (int i = 1; i <= N; i++) {
		if (dp[i] != res) {
			res = dp[i];
			cnt++;
		}
	}
	cout << cnt << "\n";
	return 0;
}

피드백

계속 런타임에러 나서 ㅋㅋ 뭔가 싶어서 백준문제에 질문까지 했다.. 알고보니 Find 함수할때 else 일 때 return을 안해서 나는 거였다 머쓱-
그러고도 틀렸습니다가 뜨길래, 아까 런타임에러 해결하려고 여러가지 반례 데이터를 넣었는데 순서 상관없이 넣을 때 답이 틀리게 나온 걸 알았다.
그래서 vector에 넣어 sort로 정리한 후에 하니깐 통과했다