[C++/31937] 로그프레소 마에스트로

---

⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.

---

이렇게 쉬운 문제가 왜 정답률이 29퍼밖에 안되지? 했던 나를 반성하는 시간이였고, 아침에 풀었더니 정신없어서 문제를 제때 풀지 못했던것 같습니다. 그래서 천천히 다시 글을 읽어보면서 문제를 해결했는데, 원인을 천천히 파악을 해보겠습니다.

일단 간단하게 설명하자면? 첫번째 감염된 컴퓨터를 찾는 문제입니다. 그래서 이 문제에서 주어지는 입력값들은 이러합니다.

컴퓨터의 개수 N, 파일 전송 로그의 개수 M, 컴퓨터의 개수 K가 주어지고, K개의 감염된 컴퓨터를 보여줍니다. 그리고 M개의 로그를 보여주게 되는데요? 여기에서 M개의 로그는 t의 시간에 a의 컴퓨터가 b의 컴퓨터에게 파일을 전송하는데 이때 감염된 컴퓨터라면? 바이러스를 보내게되어 b도 바이러스에 감염되게 됩니다. 그리고 t는 유일한 시간이고, a와 b는 같은 컴퓨터에게 전송하지 않습니다.

입력값 N의 범위는 1 <= N <= 1,000이고 M은 1 <= M <= 10,000입니다. 그래서 주어진 문제들에서 시간초과가 날 정도로 데이터를 살펴볼 필요는 없습니다. 바로 해결을 해보겠습니다.

첫번째는 K개의 감염된 컴퓨터의 존재입니다. 처음에는 감염된 컴퓨터의 값을 알고, 차례대로 로그가 주어진다면? 첫번째로 감염된 컴퓨터를 쉽게 찾을 수 있지 않을까? 였습니다. 하지만, 문제가 풀리지 않자 다시 생각을 해본 결과, 컴퓨터가 1초에 감염될 수도 있고, 2초,3초...M초에 감염이 될 수도 있기 때문에, 시작하자마자 감염된다는 보장이 없다는 것입니다.

그리하여, K개의 범위를 주목했습니다. K는 1 <= K <= N 입니다. 즉 1,000개까지가 된다는 말입니다. 그리고 1000개의 컴퓨터를 전부 살펴보면서 M개의 로그를 살펴보는데 M의 범위의 최대값은 10,000까지입니다. 즉 1,000 * 10,000을 하면? 
10,000,000번의 시간이 걸리고 이는 천만밖에 되지 않기 때문에 풀수 있습니다.

그리고 첫번째 감염된 컴퓨터를 고르고 전체를 골랐을때 K개의 컴퓨터가 나왔다면? 정답이다 라고 생각을 했습니다.

하지만, K개가 원하는 컴퓨터가 감염이 되어야 하기때문에 다시 K개의 컴퓨터가 전부 감염이 되어 있는지 체크를 해야하는 시간이 발생했고, 그리하여 최대는 천만번 + K번이 되어 천만K번이 될 것입니다. 그렇게 문제를 해결할 수 있었습니다.

문제를 처음에 너무 쉽게 접근했고, 그리고 문제를 다시 천천히 생각을 해본 결과 정답을 찾을 수 있었습니다. 문제 푸는 실력이 남아있을 줄 알았는데 논리적으로 생각하는 것은 조금이라도 연습을 덜하면 감각이 떨어지는 것 같습니다. 앞으로 더 노력해야겠습니다.

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>

#define MAX 1010
using namespace std;

struct INFO{
	int time;
	int from;
	int to;
};

int n,m,k,visited[MAX],cur[MAX];

vector<int> com;
vector<INFO> v;

void init() {
	
	cin >> n >> m >> k;
	
	for(int i = 0; i < k; i++){
		int computer; cin >> computer;
		com.push_back(computer);
		visited[computer] = 1;
	}
	
	for(int i = 0; i < m; i++){
		
		int t,f,to; cin >> t >> f >> to;
		
		v.push_back({t,f,to});
	}
	
	memset(cur,0,sizeof(cur));
	
}

bool comp(INFO& a, INFO& b){
	return a.time < b.time;
}

int main() {
	
	init();
	sort(v.begin(), v.end(), comp);
	
	int cnt = 0;
	for(int i = 0; i < com.size(); i++){
		
		memset(cur,0,sizeof(cur));
		int computer = com[i];
		cur[computer] = 1;
		cnt = 1;
		
		for(int i = 0; i < v.size(); i++){
		
			int from = v[i].from;
			int to = v[i].to;
			
			if(cur[from] && !cur[to]){
				cnt++;
				cur[to] = 1;
			}
			
		}	
		
		if(cnt == com.size()){
			int chk = 1;
			for(int i = 0; i < com.size(); i++){
				if(!cur[com[i]]) chk = false;
			}
			
			if(chk){
				cout << com[i];
				return 0;
			}
		}
		
	}
	
	
	
	return 0;
}