[백준]1240번 노드사이의 거리

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

1240번: 노드사이의 거리

문제

N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.

입력

첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리(10,000 이하의 정수)를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 M개의 노드 쌍이 한 줄에 한 쌍씩 입력된다.

출력

M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다.

---

간단한 플로이드 와샬 문제였다. 트리로 생각하지 않고 단순 그래프로 보고 인접 행렬을 채운 다음 정보를 업데이트해준다. 그다음 들어오는 쿼리에 대한 배열 값을 출력한다.

#include <iostream>
#include <string>

using namespace std;
int N, M;
int arr[1010][1010] ;

int main() {
	cin >> N >> M;

	for (int i = 0; i <= N; i++) for (int j = 0; j <= N; j++) arr[i][j] = 987654321;
	int a, b,d;
	for (int i = 0; i < N-1; i++) {
		cin >> a >> b >>d;
		arr[a][b] = d;
		arr[b][a] = d;
	}

	for (int k = 1; k <= N; k++) {
		for (int i = 0; i <= N; i++) {
			for (int j = 0; j <= N; j++) {
				if (arr[i][k] + arr[k][j] < arr[i][j])
					arr[i][j] = arr[i][k] + arr[k][j];
			}
		}
	}

	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		cout << arr[a][b] << "\n";
	}
	return 0;
}

---

골드 5 문제를 골라서 풀었는데 딱 보자마자 아는 문제여서 양심의 가책을 느꼈지만 그래도 푼 건 푼 거니깐 포스팅을 했다!

아프고 난 뒤로 공부가 하기 정말 귀찮아지는 것 같다. 공부할 수 있는 것은 굉장히 많은데 중간에 막히면 하기가 싫어져 다음날로 미루게 된다. 강릉에 있을 때는 부모님이 해주신 밥을 먹고 충분히 쉬면 공부할 시간이 굉장히 많았는데 서울 집으로 다시 올라오니 집안일도 하고 밥도 먹고 하니 은근히 힘에 부친다. 

학기 중에는 빨리 방학을 했으면 좋겠다고 생각했는데 방학이 끝날 때쯤 되니깐 학교 과목 공부가 슬슬 하고 싶어 진다! 적절한 방학과 학기의 밸런스인 것 같다. 저번 학기가 끝나고 다음 가을 학기는 휴학을 하면서 할 수 있는 공부를 하려고 했는데 방학을 계절학기를 빼면 2개월도 하지 않은 것 같은데 슬슬 지겹다. 2학기 휴학은 학교를 다니면서 조금 더 고민해봐야겠다!