[이분탐색/DFS] 백준 1939번 : 중량제한 - C/C++

 

www.acmicpc.net/problem/1939

1939번: 중량제한

- 연결리스트(메모리 제한), DFS + 이분탐색(시간제한) 으로 구현하였습니다.

  (입출력 외 라이브러리를 사용하지 않은 구현입니다.)

 

#include <stdio.h>

int N, M;
int start, end;

bool visit[10001];

struct Bridge {
	int linked, weight;
	Bridge* next;
} b[200002];
Bridge* bridgeList[10001];
int bIndex = 0;

Bridge* alloc(int linked, int weight) {
	b[bIndex].linked = linked;
	b[bIndex].weight = weight;
	return &b[bIndex++];
}

bool dfs(int curIndex, int limit) {
	if (visit[curIndex]) return false;

	visit[curIndex] = true;
	if (curIndex == end) return true;

	for (Bridge* pp = bridgeList[curIndex]; pp; pp = pp->next) {
		if (pp->weight >= limit) {
			if (dfs(pp->linked, limit)) {
				return true;
			}
		}
	}
	return false;
}

int main() {
	scanf("%d %d", &N, &M);

	int a, b, c;
	int maxInput = -1;
	for (int i = 0; i < M; ++i) {
		scanf("%d %d %d", &a, &b, &c);

		Bridge* aBridge = alloc(b, c);
		aBridge->next = bridgeList[a];
		bridgeList[a] = aBridge;

		Bridge* bBridge = alloc(a, c);
		bBridge->next = bridgeList[b];
		bridgeList[b] = bBridge;

		if (c > maxInput) maxInput = c;
	}

	scanf("%d %d", &start, &end);

	int left = 1;
	int right = maxInput;
	int ans;

	while (left <= right) {
		int mid = (left + right) / 2;

		for (int i = 0; i < 10001; ++i) visit[i] = false;

		if (dfs(start, mid)) {
			ans = mid;
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}

	printf("%d", ans);
}