DFS에서 visited의 존재는 속도를 더 빠르게 해주나요? (... - 인프런

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! 
- 먼저 유사한 질문이 있었는지 검색해보세요. 
- 서로 예의를 지키며 존중하는 문화를 만들어가요. 
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

안녕하세요. 항상 좋은 해설 감사드립니다.

제가 1325번을 풀 때 처음엔 visited없이 풀었습니다. (아래와 같은 코드를 제출했습니다.)

(arr은 선생님 코드의 dp와 같습니다, dfs는 본인이 아닌 자식노드부터 세는 것으로 잡았습니다.)

[시간초과]가 난 소스 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <climits>
using namespace std;

int n, m, a, b, maxN = INT_MIN;
vector<int> v[10004];
int arr[10004];

int dfs(int here) {
	int ret = 0;
	if(v[here].size()==0) return 0;
	for(int there : v[here]) {
		ret++;
		ret += dfs(there);
	}
	return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		cin >> a >> b;
		v[b].push_back(a);
	}
	
	for(int i = 1; i <= n; i++) {
		arr[i] = dfs(i);
		maxN = max(maxN, arr[i]);
	}
	
	for(int i = 1; i <= n; i++) {
		if(arr[i] == maxN) cout << i << ' ';
	}
	
	return 0;
}

그런데 [시간초과]가 나오길래 선생님 해답을 보니

visited의 유무가 차이가 나더라구요.

그래서 선생님의 해답을 모방해서 visited를 dfs함수에 살려 넣었는데 이번엔 통과했습니다.(아래와 같은 코드입니다.)

그래서 'visited가 있으면 속도를 더 빠르게 해줄정도로 유의미한 존재인가?' 싶어서 여쭤보려 합니다.

[맞았습니다]가 나온 이번 코드

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <climits>
#include <cstring>
using namespace std;

// visited 배열 삽입 
int n, m, a, b, visited[10004], maxN = INT_MIN;
vector<int> v[10004];
int arr[10004];

int dfs(int here) {
	visited[here] = 1;
	int ret = 0;
	if(v[here].size()==0) return 0;
	for(int there : v[here]) {
		if(visited[there]) continue;
		ret++;
		ret += dfs(there);
	}
	return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		cin >> a >> b;
		v[b].push_back(a);
	}
	
	for(int i = 1; i <= n; i++) {
		memset(visited, 0, sizeof(visited));
		arr[i] = dfs(i);
		maxN = max(maxN, arr[i]);
	}
	
	for(int i = 1; i <= n; i++) {
		if(arr[i] == maxN) cout << i << ' ';
	}
	
	return 0;
}

안녕하세요. yunbinni님ㅎㅎ

먼저 2주차 강의를 한번 더 보시는 것을 추천드리구요.

제가 질문하나 드리겠습니다.

visited 없이 "방문한 정점을 다시 방문하지 않기"를 어떻게 구현하실건가요?

만약 DAG tree형태라면 어느정도는 가능하지만 이 문제는 "그래프"인데요.

visited는 "방문한 정점을 다시 방문하지 않기 위한 장치" 인 것입니다.

visited 배열을 걸어서 한 것과 안한것을

int dfs(int here) {

cout << here << '\n';

int ret = 0;

이런식으로 이부분에 here 디버깅을 통해 어느 정점들을 방문하는지 확인해보시면 금방 어떤 느낌인지 알 수 있으실겁니다.

또 질문사항있으시면 언제든 말씀 부탁드립니다.

감사합니다.

강사 큰돌 올림.

인프런 커뮤니티 질문&답변

DFS에서 visited의 존재는 속도를 더 빠르게 해주나요? (1325번)