2-S 재질문 드립니다 :)
안녕하세요 선생님 🙂
이전에 풀었던 문제들을 전부 다시 풀어보는 중입니다. 다시 풀어보니 이전에는 안보였던 부분들이 보이기 시작하더라구요.
2가지 질문이 있습니다.
http://boj.kr/2560aa9844964379b8e8c4b30e917888
위의 풀이는 visited배열을 사용하지 않고 풀이한 방법입니다. 1부터 5까지 놓여있는 테스트케이스만 놓고 생각해보면 visited배열로 방문처리를 안하더라도 겹치는 인덱스가 없습니다. 따라서 방문처리를 안하는 것이 오히려 낫다라는 생각을 했는데요, 시간초과가 되었습니다. 이유가 무엇인지 모르겠어서 질문 드립니다.
http://boj.kr/10e79d578a2c4aefbfd07995bdb94025
위의 풀이는 temp배열을 사용하지 않고 풀이한 방법입니다. temp배열을 선언하지 않고 그 자리에 DFS(i)를 넣어도 결과는 같을 것이라고 생각했지만, for문에서 DFS(i)를 출력하면 1번 인덱스부터 N번 인덱스까지 전부 1이 나오더라구요. 아무리 생각해도 이해가 되지가 않습니다.
조언 부탁드립니다..!!
답변 1
1
안녕하세요 유태님 ㅎㅎ
int DFS(int idx)
{
int cnt = 1;
for (const auto& v : vec[idx])
{
cnt += DFS(v);
}
return cnt;
}이럴 경우 사이클이 있는 경우 무한 탐색이 되버립니다.
for (int i = 1; i <= N; i++)
{
if (mx == DFS(i)) cout << i << " ";
}이럴 경우에 if문 실행시 DFS가 실행되는데 이렇게 하면 상상한 DFS가 올바르게 동작하지 않습니다. visited 초기화 -> DFS 이렇게 구축해야 합니다.
temp 배열이 DP 말씀하시는 것 같은데요. 이렇게 결과값을 모아두어야 불필요하게 반복되는 DFS를 방지할 수 있습니다
#include <bits/stdc++.h>
using namespace std;
vector<int> v[10001];
int dp[10001], mx, visited[10001], n, m, a, b;
int dfs(int here) {
visited[here] = 1;
int ret = 1;
for(int there : v[here]){
if(visited[there]) continue;
ret += dfs(there);
}
return ret;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(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));
dp[i] = dfs(i);
mx = max(dp[i], mx);
}
for (int i = 1; i <= n; i++) if (mx == dp[i]) cout << i << " ";
return 0;
}
감사합니다.
살구 클럽에 대한 질문있습ㄴ디ㅏ
0
6
0
교안 158페이지 문의드립니다
0
24
2
코딩살구클럽 관련 건의사항
0
53
1
코살에 19942 다이어트 문제에 N의 범위가 빠져있슴니다
0
26
1
진행 방법 질문드립니다!
0
56
2
2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.
0
59
2
2주차 개념#12 트리 순회
0
28
2
백준사이트가 종료된다고 합니다.
0
288
2
백준 서비스 종료
9
894
1
sk 하이닉스 코테 대비
0
370
2
3-G 최댓값 질문
0
51
1
모듈러 연산 값이 10이 아닌 경우도 있지 않나요?
0
83
2
3-I 코드 질문드립니다.
0
62
2
3-N 질문 있습니다.
0
66
2
학습방법
0
102
2
4-H 질문 있습니다 (코드 리뷰)
0
66
2
코딩테스트 어디까지 준비해야 하는지 질문이 있습니다.
0
172
2
2-O 반례가 무엇일지 어떤 부분이 틀렸는지 잘 모르겠습니다.
0
69
2
2주차 개념 #4-2. 인접행렬 질문있습니다.
0
64
2
1-A 문제풀이 후 궁금한 점이 생겨서 질문드립니다.
0
51
2
조합 재귀 풀이 확인 해주시면 감사하겠습니다.
0
68
2
함수별 시간복잡도
0
73
2
3-h 질문입니다.
0
49
1
안녕하세요 선생님. 시간 복잡도 4번 질문있습니다.
0
53
2