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

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

14938번: 서강그라운드

 플로이드 와샬 알고리즘을 통해 쉽게 풀 수 있는 문제다. 이번 문제를 풀 때는 코드를 가독성 좋게 나타내기 위해, 문제 풀이를 같은 기능으로 하는 몇 부분으로 나누어 함수로 나타내었다. 이렇게 하면 메인 함수에서 프로그램의 흐름을 쉽게 파악할 수 있을 뿐만 아니라 가독성도 좋아서 디버깅할 때 편할 것 같다. 디버깅을 위해 사용하는 함수도 별도로 분리해 놓아서 다른 함수들과 헷갈리지 않도록 했다. 이 문제의 첫 시도와 두 번째 시도에서 약 6%에서 WA를 받았다. 처음에는 각 노드 간 거리를 입력 받을 때, 두 노드 사이에 둘 이상의 경로가 있을 때를 고려하지 않아 틀렸다고 생각했다. 그래서 입력 받은 길이가 기존에 저장된 길이보다 짧을 때에만 저장하도록 코드를 수정했고 그래도 WA를 받자 인터넷에서 답안을 확인했다.

https://imnotabear.tistory.com/339

[백준 14938] 서강그라운드 (C++)

 코드를 봐도 내가 제출한 코드랑 다른 점을 찾기 어려웠지만, 이내 곧 찾았다. 거리가 M 이내의 노드에서 아이템을 수집할 수 있었는데, 내 코드에선 M 미만의 노드만 아이템의 개수를 누적했다. 문제를 제대로 읽지 않아 생긴 문제라고 할 수 있겠다. 사소한 실수로 WA를 받지 않도록 더 많은 노력이 필요할 것 같다.

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"
#define VI vector<int>
#define VVI vector<VI>
#define VVVI vector<VVI>

/* declare variables here */
int N, M, R;
VI Items;
VVI Length;

/* define debug functions here */
void print() {
	FOR(i, N) {
		FOR(j, N) {
			cout << fixed;
			cout << setw(10) << Length[i][j];
		}
		cout << EL;
	}
	cout << EL;
}

/* define functions here */
void reduction() {
	FOR(via, N) FOR(from, N) FOR(to, N)
		if (Length[from][via] + Length[via][to] < Length[from][to])
			Length[from][to] = Length[from][via] + Length[via][to];
}

int find_max_amount() {
	int max_amount = 0;
	FOR(i, N) {
		int amount = 0;
		FOR(j, N)
			if (Length[i][j] <= M)
				amount += Items[j];
		if (amount > max_amount)
			max_amount = amount;
	}
	return max_amount;
}

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	/* Write input codes here */
	cin >> N >> M >> R;
	Items = VI(N);
	FOR(i, N)
		cin >> Items[i];
	Length = VVI(N, VI(N, INF));
	FOR(i, N)
		Length[i][i] = 0;
	FOR(i, R) {
		int u, v, w;
		cin >> u >> v >> w;
		if (w < Length[u - 1][v - 1]) {
			Length[u - 1][v - 1] = w;
			Length[v - 1][u - 1] = w;
		}
	}

	/* Write solution codes here */
	reduction();
	cout << find_max_amount() << EL;

	return 0;
}