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
7
1
코딩살구클럽 승인
0
18
2
DP 경우의 수 설명이 이해가 되지 않습니다.
0
27
2
3-F 채점 관련 질문
0
24
1
BFS, DFS 활용이 되는 상황에서의 방향성
0
28
2
코딩살구클럽 승인
0
41
2
코딩살구클럽승인
0
33
3
코딩살구클럽 승인
0
48
2
3-D 관련 질문
0
35
2
코살구 회원가입 문의
0
43
2
코살구 로그인 문제
0
65
2
3-A 문제 풀이 관련 질문
0
53
3
2-O 질문 있습니다
0
38
2
2-T 문제에 관한 질문
0
40
2
코딩 살구 클럽 접속 및 사용방법 문의
0
61
2
안녕하세요~. 현재 코살코딩클럽 사이트가 접속이 안됩니다~
0
64
2
코딩살구클럽 로그인문제
0
78
3
코딩 살구 클럽 로그인 문제
0
82
2
2-J 채점관련 질문
0
65
3
코딩 살구 클럽 Python 지원 가능 여부
0
77
1
살구클럽 아이디 없음 문제
0
76
1
1-O 코딩살구클럽 채점관련 질문
0
60
2
히든 테스트 케이스가 사라졌습니다
0
57
1
채점서버 혹시 다른 언어 지원도 가능하게 해주실 수 있나요
1
74
2