[C++]G5 백준 15591 - MooTube (Silver)

※문제 이름에 Silver가 있지만 난이도는 실버가 아님;;

1. 문제 링크

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

문제 풀이 소요 시간 : 1시간 37분

시도 횟수 : 3

 

2. 문제 설명

난이도 : G5

사용 알고리즘 : DFS

소튜브에서 유사도에 따라 추천 가능한 영상 수를 출력하는 문제

 

3. 초기 풀이 방식

DFS로 접근했다.

첫 풀이는 아래와 같다

n-1개의 유사도 정보를 토대로 모든 영상에 대해 각 영상의 유사도를 기록한다.(map 활용)
q개의 질문이 들어오면,
질문의 동영상마다 다른 동영상과의 유사도를 반복문을 통해 확인하여 추천 가능한 영상을 출력한다.

#include<iostream>
#include<vector>
#include<map>
#include<stack>
#include<algorithm>

using namespace std;
vector<pair<int, int>> v[5001];
map<pair<int, int>, int> usado;

void dfs(int st) {
	bool isvisit[5001] = { 0, };
	stack<int> s;
	s.push(st);
	while (!s.empty()) {
		if (isvisit[s.top()]) {
			s.pop();
			continue;
		}
		isvisit[s.top()] = 1;
		int tmp = s.top();
		s.pop();
		for (int i = 0; i < v[tmp].size(); i++) {
			if (!isvisit[v[tmp][i].first]) {
				int q1 = v[tmp][i].first;
				int q2 = v[tmp][i].second;
				s.push(q1);
				int prev = (st < tmp) ? usado[{st, tmp}] : usado[{tmp, st}];

				if (st < q1 && usado[{st, q1}] == 0) usado[{st, q1}] = min(q2, prev);
				else if (st > q1 && usado[{q1, st}] == 0) usado[{q1, st}] = min(q2, prev);
			}
		}
	}
}

int main() {
	int n, q;
	cin >> n >> q;

	for (int i = 0; i < n-1; i++) {
		int a, b, r;
		cin >> a >> b >> r;
		if (a > b) swap(a, b);
		v[a].push_back({ b,r });
		v[b].push_back({ a,r });
		if (usado[{a, b}] == 0 || usado[{a, b}] > r) usado[{a, b}] = r;
	}
	for (int i = 0; i < n; i++) {
		dfs(i);
	}
	for (int i = 0; i < q; i++) {
		int a, b;
		int cnt = 0;
		cin >> a >> b;
		for (int j = 1; j < b; j++) {
			if (usado[{j, b}] >= a) cnt++;
		}
		for (int j = b + 1; j <= n; j++) {
			if (usado[{b, j}] >= a) cnt++;
		}
		cout << cnt << "\n";
	}
}

 

4. 풀이 실패 원인 분석 + 해결

시간 초과가 발생했다!

혹시나 싶어 dfs 함수 실행 부분을 질문 입력 후에 실행하게 바꿔보았지만 이 또한 시간초과가 발생했다

(시간초과 또 뜨는 건 예상하긴 했다)

 

자 그래서 어떻게 바꿨냐!

 

 

생각해보니 모든 영상에 대한 유사도를 미리 구할 필요가 없었다.
입력값을 저장만 해두고,
질문이 들어오면 그때마다 dfs를 실행하는 방식으로 실행
+
입력받은 K값을 dfs 함수에 함께 인자로 넘겨주어,
탐색 과정에서 유사도가 K보다 작다면 탐색 중단(불필요한 탐색 방지)
탐색 과정에서 cnt 변수를 이용해 동영상을 세고 그 값을 반환 후 출력!

 

최종 제출 코드는 아래와 같습니당

#include<iostream>
#include<vector>
#include<map>
#include<stack>
#include<algorithm>

using namespace std;
vector<pair<int, int>> v[5001];

int dfs(int cut, int st) {
	bool isvisit[5001] = { 0, };
	stack<int> s;
	s.push(st);
	int cnt = 0;
	while (!s.empty()) {
		if (isvisit[s.top()]) {
			s.pop();
			continue;
		}
		isvisit[s.top()] = 1;
		int tmp = s.top();
		s.pop();
		for (int i = 0; i < v[tmp].size(); i++) {
			if (!isvisit[v[tmp][i].first]) {
				int q1 = v[tmp][i].first;
				int q2 = v[tmp][i].second;
				if (q2 < cut) continue;
				s.push(q1);
				cnt++;
			}
		}
	}
	return cnt;
}

int main() {
	int n, q;
	cin >> n >> q;

	for (int i = 0; i < n-1; i++) {
		int a, b, r;
		cin >> a >> b >> r;
		if (a > b) swap(a, b);
		v[a].push_back({ b,r });
		v[b].push_back({ a,r });
	}
	for (int i = 0; i < q; i++) {
		int a, b;
		cin >> a >> b;
		int cnt = dfs(a, b);
		cout << cnt << "\n";
	}
}

 

<오늘의 TMI>
학기 중에 브론즈 문제만 풀다가 종강한 기념 다시 코테 준비를 시작해보려 오랜만에 골드 문제를 건드려봤는데 DFS 어떻게 하는지 막막했던 내 자신 반성하기