[백준 C++] 14938번 : 서강그라운드

1. 문제

 

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

14938번: 서강그라운드

2. 알고리즘 분류

• 그래프 이론
• 데이크스트라
• 플로이드-워셜

 

3. 소스 코드

3-1) 일반 DFS 활용

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int max_item;	// 최대 아이템 갯수
int items[101];	// 각 지역의 아이템 갯수
bool visited[101];	// 방문한 지역 체크
vector<pair<int, int>> graph[101];	// 지역 간의 거리 그래프

void dfs(int area, int range) {
	for (int i = 0; i < graph[area].size(); i++) {
		int dest = graph[area][i].first;
		int dist = graph[area][i].second;

		if (range < dist) continue;	// 갈 수 있는 수색범위보다 거리가 더 큰 경우 skip
		
		visited[dest] = true;
		dfs(dest, range - dist); // 다음 지역 탐색
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	// 입력
	// n : 지역의 개수, m : 수색범위, r : 길의 개수
	int n, m, r;
	cin >> n >> m >> r;

	for (int i = 1; i <= n; i++)
		cin >> items[i];

	for (int i = 0; i < r; i++) {
		int a, b, l;
		cin >> a >> b >> l;

		graph[a].push_back({ b, l });
		graph[b].push_back({ a, l });
	}

	// 문제 해결(DFS 알고리즘)
	for (int i = 1; i <= n; i++) {
		
		// 초기화
		int cnt_item = 0;
		for (int j = 0; j < 101; j++)
			visited[j] = false;

		// 각 지역 탐색(DFS)
		visited[i] = true;
		dfs(i, m);

		// 탐색한 지역의 아이템 갯수 더하기
		for (int j = 0; j < 101; j++)
			if (visited[j]) cnt_item += items[j];

		// 최댓값 갱신
		max_item = max(max_item, cnt_item);
	}
	
	// 출력
	cout << max_item;

	return 0;
}

 

3-2) 플로이드 워셜 알고리즘 활용

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 987654321
using namespace std;

int n, m, r;	// n : 지역의 개수, m : 수색범위, r : 길의 개수
int max_item;	// 최대 아이템 갯수
int items[101];	// 각 지역의 아이템 갯수
bool visited[101];	// 방문한 지역 체크
int graph[101][101];	// 지역 간의 거리 그래프

// 특정 지역으로 갈 수 있는 최단거리 구하는 알고리즘
void floyd_warshall() {
	for (int k = 1; k <= n; k++)	// 거쳐가는 지역
		for (int i = 1; i <= n; i++)	// 시작지
			for (int j = 1; j <= n; j++)	// 종착지
				if (graph[i][k] + graph[k][j] < graph[i][j]) // 거쳐가는 경로가 더 빠를 경우 갱신
					graph[i][j] = graph[i][k] + graph[k][j];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	// 초기화
	for (int row = 0; row < 101; row++)
		for (int col = 0; col < 101; col++)
			if (row == col) graph[row][col] = 0;
			else graph[row][col] = INF;

	// 입력
	cin >> n >> m >> r;

	for (int i = 1; i <= n; i++)
		cin >> items[i];

	for (int i = 0; i < r; i++) {
		int a, b, l;
		cin >> a >> b >> l;

		graph[a][b] = l;
		graph[b][a] = l;
	}

	// 문제 해결(플로이드 워셜 알고리즘)
	floyd_warshall();	// 최단거리 구하는 알고리즘

	for (int start = 1; start <= n; start++) {
		int cnt_item = 0;

		// 시작점으로부터 특정 지역까지 갈 수 있는 최단거리가 수색범위내 일때, 아이템 갯수들 더하기
		for (int j = 1; j <= n; j++)
			if (graph[start][j] <= m) cnt_item += items[j];

		// 최댓값 갱신
		max_item = max(max_item, cnt_item);
	}

	// 출력
	cout << max_item;

	return 0;
}

 

3-3) 다익스트라 알고리즘 활용

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 987654321
using namespace std;

int n, m, r;	// n : 지역의 개수, m : 수색범위, r : 길의 개수
int max_item;	// 최대 아이템 갯수
int items[101];	// 각 지역의 아이템 갯수
int dist[101]; // 시작점으로부터 해당 지점까지 거리
vector<pair<int,int>> graph[101];	// 지역 간의 거리 그래프

// 최단거리를 찾는 다익스트라 알고리즘
void dijkstra(int start) {
	// 현재 위치는 거리 0으로 셋팅
	dist[start] = 0;

	priority_queue<pair<int, int>> pq;
	pq.push({ start, 0 });	// 시작점 pq에 저장

	while (!pq.empty()) {
		int current = pq.top().first;
		int distance = -pq.top().second;
		pq.pop();

		if (dist[current] < distance) continue;	// 걸리는 거리가 이전에 구한 거리보다 먼 경우, skip

		// 현재 지점에서 갈 수 있는 지점 탐색
		for (int i = 0; i < graph[current].size(); i++) {
			int next = graph[current][i].first;
			int next_distance = distance + graph[current][i].second;

			// 계산한 거리가 기존의 계산한 거리보다 짧은 경우, 갱신
			if (next_distance < dist[next]) {
				dist[next] = next_distance;
				pq.push({ next, -next_distance });
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	// 입력
	cin >> n >> m >> r;

	for (int i = 1; i <= n; i++)
		cin >> items[i];

	for (int i = 0; i < r; i++) {
		int a, b, l;
		cin >> a >> b >> l;

		graph[a].push_back({ b, l });
		graph[b].push_back({ a, l });
	}

	// 문제 해결(다익스트라 알고리즘)
	// 모든 지점에서 시작해보기
	for (int start = 1; start <= n; start++) {

		// 거리를 모두 무한으로 초기화
		for (int i = 1; i <= n; i++)
			dist[i] = INF;

		// 최단거리를 구하기 위한 다익스트라 알고리즘
		dijkstra(start);

		// 각 지점까지 가는데 걸리는 거리가 수색 범위내 일 경우, 아이템 갯수 더하기
		int cnt_item = 0;
		for (int i = 1; i <= n; i++)
			if (dist[i] <= m) cnt_item += items[i];

		// 최댓값 갱신
		max_item = max(max_item, cnt_item);
	}

	// 출력
	cout << max_item;

	return 0;
}

 

4.  유용한 문법 및 알고리즘

4-1)  DFS 알고리즘(깊이 우선 탐색, 그래프 탐색 방법)

void dfs(int area, int range) {
	for (int i = 0; i < graph[area].size(); i++) {
		int dest = graph[area][i].first;
		int dist = graph[area][i].second;

		if (range < dist) continue;	// 갈 수 있는 수색범위보다 거리가 더 큰 경우 skip
		
		visited[dest] = true;
		dfs(dest, range - dist);
	}
}

 

4-2) 플로이드 워셜 알고리즘

// 특정 지역으로 갈 수 있는 최단거리 구하는 알고리즘
void floyd_warshall() {
	for (int k = 1; k <= n; k++)	// 거쳐가는 지역
		for (int i = 1; i <= n; i++)	// 시작지
			for (int j = 1; j <= n; j++)	// 종착지
				if (graph[i][k] + graph[k][j] < graph[i][j]) // 거쳐가는 경로가 더 빠를 경우 갱신
					graph[i][j] = graph[i][k] + graph[k][j];
}

 

4-3) 다익스트라 알고리즘

// 최단거리를 찾는 다익스트라 알고리즘
void dijkstra(int start) {
	// 현재 위치는 거리 0으로 셋팅
	dist[start] = 0;

	priority_queue<pair<int, int>> pq;
	pq.push({ start, 0 });	// 시작점 pq에 저장

	while (!pq.empty()) {
		int current = pq.top().first;
		int distance = -pq.top().second;
		pq.pop();

		if (dist[current] < distance) continue;	// 걸리는 거리가 이전에 구한 거리보다 먼 경우, skip

		// 현재 지점에서 갈 수 있는 지점 탐색
		for (int i = 0; i < graph[current].size(); i++) {
			int next = graph[current][i].first;
			int next_distance = distance + graph[current][i].second;

			// 계산한 거리가 기존의 계산한 거리보다 짧은 경우, 갱신
			if (next_distance < dist[next]) {
				dist[next] = next_distance;
				pq.push({ next, -next_distance });
			}
		}
	}
}