[1039] 중량 제한, c++

[1039] 중량제한

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

1939번: 중량제한

한줄 후기 : 옛날에 열심히 했었네..

 

#include <iostream>
#include <vector>
#include <cstring>
#include <utility>
#include <algorithm>
using namespace std;
vector<pair<int,int> > island[10001];
int n, m, x, y;
bool visit[10001] = {false};
int dfs(int mid, int x){
	visit[x] = true;
	for(int i=0; i<island[x].size(); i++){
		if(visit[island[x][i].first] || island[x][i].second < mid){
			continue;
		}
		dfs(mid, island[x][i].first);
	}
	return visit[y];
}
int main(){
	int a,b,c;
	int l=0,r=0,mid, ans=1;
	scanf("%d %d", &n, &m);
	//memset(island, -1, sizeof(island));
	for(int i=0; i<m; i++){
		scanf("%d %d %d", &a,&b,&c);
		island[a].push_back(make_pair(b,c));
		island[b].push_back(make_pair(a,c));
		r = max(r,c);
	}
	scanf("%d %d", &x, &y);
	while(l<=r){
		mid=(l+r)/2;
		memset(visit,false,sizeof(visit));
		if(dfs(mid,x)){
			l = mid+1;
			ans=max(ans,mid);
		}
		else	r = mid-1;
	}
	printf("%d", ans);
	return 0;
}

1번 시도에 통과는 했는데 엄청 어려웠던 것 같음

문제가 어렵기 보다는 코드 짜는게 까다로운?? 무튼 대충 문제는 여러개의 섬을 연결하는 양방향 가중 그래프에서 주어진 공장 사이를 한번에 오갈

수 있는 무게를 출력해주면된다. 즉, 다리의 무게를 넘는 물건은 옮길 수 없다.

옮길 무게 기준을 이분 탐색으로 정해주면 된다. 그리고 나머지는 그래프이기 때문에 그 무게를 가지고 dfs 를 돈다.

​

1. 마지막에 내가 도착해야할 공장의 visit 배열이 true 라면 -> 그 무게로 다리를 건널 수 있음 이니까 다음 mid(l = mid + 1) 로 다시 돌아준다.

2. visit 이 false 라면 -> 그 무게를 가지고 내가 갈 공장에 도착 할 수 없음 그러니까 mid를 더 작게 해준다. (r = mid - 1)

​

이때 중요한 건 다른 그래프 문제랑 은 다르게 visit 배열은 항상 한번 dfs를 돌면 초기화 해줘야 한다. 왜냐면 다른 무게로 또 그 공장에 방문해야 하니까~