1325 - 효율적인 해킹

문제

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> v[10004];
bool visited[10004];
int n,m,a,b;
int res[10004];
int mx;

int dfs(int y){
	visited[y] = 1;
	int ret = 1;
	for(int a : v[y]){
		if(visited[a]) continue;
		ret += dfs(a); 
	}
	return ret;
}

int main(){
	mx = 0;
	cin >> n >> m;
	while(m--){
		cin >> a >>b;
		v[b].push_back(a);
	}
	for(int i = 1; i <=n; i++){
		memset(visited, 0, sizeof(visited));
		res[i] = dfs(i);
		mx = max(res[i], mx);
	}
	for(int i = 1; i <=n; i++){
		if(mx == res[i]) cout << i << " ";
	}
	return 0;
}

풀이

위 그림과 같이 설계를 했다.
그래서 처음에 작성한 코드는 max 값을 변수에 할당하고 그 변수를 조건에 맞춰서 아래와 같은 코드를 작성했다.

for(int i = 1; i <= n; i++){
		memset(visited, 0, sizeof(visited));
		d = dfs(i);
		if(r.size()){
			if(d > temp){
			r.pop_back();
			r.push_back(i);
			}
		}else r.push_back(i);
		if(d == temp){
			r.push_back(i);
		}
		temp = max(d,temp);
}
	sort(r.begin(), r.end());
	for(int k : r) cout << k << " ";

주어진 TC는 통과했는데 오류가 있다고 한다. 그래서 변수 자체를 조건문에 넣는게 아니라 전부를 한 배열에 넣되 max 값을 계속 얻어내고 max값과 배열을 비교해서 출력하도록 한다.

dfs 함수는 연결된 컴퓨터마다 1을 추가해줘야 하는데 이 부분은 컴퓨터 하나마다 1값을 주고 ret을 반환하는데 이 ret을 계속 더하도록 하였다.
그렇다면 연결된 컴퓨터 갯수만큼 ret을 반환하기 때문이다.

결과

후기

아 진짜 엄청 틀렸다.
dfs문에 visited로 조건을 안걸었더니 시간 초과가 났고
출력값을 변수에 넣어서 조건문을 걸었을 때는 오답이었다.
최대값이 10만인데 조건을 안걸어주니 시간초과가 나는거 같았다.
오답인 이유는 놓친 조건문이 있지 않나 싶지만 사실 맞는거 같은데 왜 자꾸 틀린다고 하는지 모르겠다.ㅋ
실버 1 문제지만 굉장히 어려웠다.