DFS에서 visited의 존재는 속도를 더 빠르게 해주나요? (1325번)
해결됨
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 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; }
- 1325
- C++
- 코테 준비 같이 해요!