DFS로 구현 시 adj 2차원 벡터 vs 벡터 배열 - goormEDU

Q&A

It is a place to ask and answer questions related to IT technology.

0
DFS로 구현 시 adj 2차원 벡터 vs 벡터 배열
profilesoybean1022
07/02/20, 03:22 PM
Question Path :
// string을 쓰는 일반 문제풀이용 템플릿 #include <bits/stdc++.h> #define SIZE 202020 using namespace std; typedef vector<int> vi; typedef vector<vector<int>> vvi; typedef vector<bool> vb; // vvb를 쓰냐 vector 배열을 쓰냐에 따라 달라진다고??? vvi adj(SIZE, vi()); //vector<int> adj[SIZE]; vb group(SIZE, false); int dfs(int idx) { // idx : 노드 idx // gidx ; 그룹 idx if (group[idx]) return 0; group[idx] = true; int num = 1; for (int i = 0; i < adj[idx].size(); i++) num += dfs(adj[idx][i]); return num; } int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); int n, m; cin >> n >> m; for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } // dfs int ans = 0, ansidx = -1; for (int i = 1; i < n + 1; i++) { int ret = dfs(i); if (ret > ans) { ansidx = i; ans = ret; } } cout << ansidx << " " << ans << '\n'; return 0; }

위 코드에서 adj를 2차원 벡터를 사용하여 구현하면 테스트케이스 4에서 런타임 에러가 나고, 벡터 배열으로 구현하면 통과됩니다. 제가 생각하기에는 2차원 벡터로 구현하게 되면 각 1차원 벡터마다 size 등의 정보가 붙는 것 때문에 조금 메모리 사용량이 늘어날 수도 있다고 보는데, 혹시 그 차이 때문에 메모리 초과가 발생하여 에러가 나는 건지 궁금하네요.