[BOJ] 11085 군사 이동

(2021년 1월 24일에 작성한 글입니다.)

 

11085번: 군사 이동

(20.08.09)

c부터 v까지 DFS를 계속 돌면서 체크하도록 했더니 시간초과.
경로가 존재하는지만 확인을 하면 되기 때문에
Union-Find(DST)를 사용하면 훨씬 간단하다!!!

우왕 짱 신기

그리고!! structure를 이용해서 푼 첫 문제인거 같다 아마
짱신기!!!!!
이제 앞으로 벡터 쓸때 pair를 여러개 하지 않아도 된다...ㅋㅋㅋㅋㅋ
앞으로 structure를 애용하게 될 거 같다

 

 

라고 과거의 내가 적어놓은 걸 봤다.

 

​한동안 MST를 완전히 잊고 살고 있었구나...

어떻게 푸는지 모르겠어서

예전에 짠 코드를 보고 이해했다...

그때의 내가 꽤 똑똑했구나.

​

MST의 최대 버전이라고 생각하면 된다

width가 큰 것부터 간선을 뽑아준 다음에

경로가 생성 됐으면 맨 마지막에 뽑은 간선의 width가 답이 된다...

​

진짜

​

신기가 방기다..!

struct Edge {
	int start, end, width;
};

bool sortby(Edge a, Edge b) {
	return a.width > b.width;
}

vector<int> par;
int GetPar(int);
void Merge(int, int);


int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int P, W;
	int C, V;

	cin >> P >> W
		>> C >> V;
	vector<Edge> edges(W + 5);
	for (int i = 0; i < W; i++) {
		cin >> edges[i].start >> edges[i].end >> edges[i].width;
	}
	sort(edges.begin(), edges.begin() + W, sortby);

	par.resize(P + 5, -1);

	for (int i = 0; i < W; i++) {
		Merge(edges[i].start, edges[i].end);
		if (GetPar(C) == GetPar(V)) {
			cout << edges[i].width << ENDL;
			break;
		}
	}

	return 0;
}

int GetPar(int x)
{
	if (par[x] == -1) {
		return x;
	}
	return par[x] = GetPar(par[x]);
}

void Merge(int x, int y)
{
	x = GetPar(x);
	y = GetPar(y);
	
	if (x != y) {
		par[x] = y;
	}
}