BOJ 1939 : 중량제한

알고리즘 문제 전체 링크

 

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

 

 

문제의 답이 되는 최대 중량을 X라고 하자.

그리고 두 섬이 연결되어 있는 것은 DFS를 이용하자.

섬 1과 섬 2가 중량 X로 다리를 건널 수 있다면, DFS(X, 섬 1)은 섬 2로 연결된다.

그러면 DFS(X, 섬 1)은 true다.

 

DFS(X + 1, 섬 1)은 반드시 false가 된다.

이유는 문제의 답이 되는 최대 중량이 X이므로, X + 1의 중량을 견딜 다리가 없기 때문이다.

 

반대로 DFS(X - 1, 섬 1)은 반드시 true가 된다.

중량 X를 견디는 다리는 최대 중량 X보다 작은 값도 견딜 수 있기 때문이다.

 

따라서 정답 X에 대해 X보다 작거나 같은 값은 섬을 연결할 수 있고,

X보다 큰 값은 섬을 연결할 수 없다.

 

그러므로 이분 탐색을 이용하여 X를 찾을 수 있다.

 

어떤 값 m을 지정하여 DFS를 실행한 후,

DFS가 true라면 m보다 작은 값은 항상 정답이고, m의 크기를 증가시킨다. (그리고 정답에 담는다.)

DFS가 false라면 m보다 큰 값은 항상 오답이고, m의 크기를 감소시킨다.

 

최종적으로 정답에 담긴 답이 X가 된다.

---

먼저 섬의 크기 N이 최대 10,000이므로 메모리 풀을 이용한 링크드 리스트로 그래프를 만든다. 

 

섬이 10,000개 이므로 HEAD는 최대 10000개, 연결된 다리가 100,000개 이므로 메모리 풀은 2배가 필요하다.

(섬 1에 섬 2를 연결하고, 섬 2에도 섬 1을 연결해야 한다.)

 

연결하는 섬(NODE)에는 연결된 섬(node)과 다리의 중량제한(weight)가 필요하다.

그리고 DFS를 이용하여 방문 표시를 할 배열 visit도 섬의 개수만큼 선언한다.

#define MAX (10000 + 500)
#define MAX_POOL (200000 + 5000)

int N, M;
int ISLAND1, ISLAND2;

typedef struct st 
{
	int node;
	int weight;
	struct st* next;
}NODE;

NODE HEAD[MAX];
NODE POOL[MAX_POOL];
int pcnt;

int visit[MAX];

void Make(int p, int c, int w)
{
	NODE* nd = &POOL[pcnt++];

	nd->node = c;
	nd->weight = w;

	nd->next = HEAD[p].next;
	HEAD[p].next = nd;
}

 

메모리 풀로 링크드 리스트를 만드는 작업은 main에서 입력을 받으면서 만든다.

그리고 가장 큰 중량 C의 값을 저장해둔다.

int main(void)
{
	int left, right, mid, ans, maxC;

	scanf("%d %d", &N, &M);

	maxC = 0;
	for (int i = 0; i < M; i++) 
	{
		int A, B, C;

		scanf("%d %d %d", &A, &B, &C);

		Make(A, B, C);
		Make(B, A, C);
		
		if (maxC < C) maxC = C;
	}
    
	scanf("%d %d", &ISLAND1, &ISLAND2);
    
    ...
    
}

 

입력을 모두 받았으면 left와 right를 정한다.

가장 작은 중량은 0이므로 left는 0이되고, right는 가장 큰 중량인 maxC로 한다.

while문을 돌면서 left가 right보다 작아질 때 까지 정답을 저장하면 된다.

DFS를 시작하기 전 visit 배열을 초기화하고, left와 right의 가운데 값을 DFS로 넘긴다.

int main(void)
{
	/* input */
	...

	left = 0, right = maxC;
	while (left <= right) 
	{
		for (int i = 1; i <= N; i++) visit[i] = 0;

		visit[ISLAND1] = 1;

		mid = (left + right) / 2;

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

	printf("%d\n", ans);

	return 0;
}

 

DFS에는 weight와 섬을 넘겨 받는다.

넘겨받은 섬의 다리가 중량을 초과하지않고, 방문하지 않은 곳에 대해 연결된 node에 섬 2가 있다면 true가 된다.

그렇지 않다면 그 섬에 대해 다시 DFS를 탐색하면 된다.

bool DFS(int w, int node) 
{
	for (NODE* p = HEAD[node].next; p; p = p->next) 
	{
		if (p->weight >= w && visit[p->node] == 0) 
		{
			visit[p->node] = 1;

			if (p->node == ISLAND2) return true;
			if (DFS(w, p->node)) return true;
		}
	}

	return false;
}

모든 섬을 탐색해도 ISLAND2를 찾지 못하면 false가 된다.

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (10000 + 500)
#define MAX_POOL (200000 + 5000)

int N, M;
int ISLAND1, ISLAND2;

typedef struct st 
{
	int node;
	int weight;
	struct st* next;
}NODE;

NODE HEAD[MAX];
NODE POOL[MAX_POOL];
int pcnt;

int visit[MAX];

void Make(int p, int c, int w)
{
	NODE* nd = &POOL[pcnt++];

	nd->node = c;
	nd->weight = w;

	nd->next = HEAD[p].next;
	HEAD[p].next = nd;
}

bool DFS(int w, int node) 
{
	for (NODE* p = HEAD[node].next; p; p = p->next) 
	{
		if (p->weight >= w && visit[p->node] == 0) 
		{
			visit[p->node] = 1;

			if (p->node == ISLAND2) return true;
			if (DFS(w, p->node)) return true;
		}
	}

	return false;
}

int main(void)
{
	int left, right, mid, ans, maxC;

	scanf("%d %d", &N, &M);

	maxC = 0;
	for (int i = 0; i < M; i++) 
	{
		int A, B, C;

		scanf("%d %d %d", &A, &B, &C);

		Make(A, B, C);
		Make(B, A, C);
		
		if (maxC < C) maxC = C;
	}

	scanf("%d %d", &ISLAND1, &ISLAND2);

	left = 0, right = maxC;
	while (left <= right) 
	{
		for (int i = 1; i <= N; i++) visit[i] = 0;

		visit[ISLAND1] = 1;

		mid = (left + right) / 2;

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

	printf("%d\n", ans);

	return 0;
}