2-S 재질문 드립니다 :)

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

한유태

작성한 질문수

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

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이 나오더라구요. 아무리 생각해도 이해가 되지가 않습니다.

조언 부탁드립니다..!!

c++코딩-테스트

답변 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;
}

감사합니다.

한유태

작성한 질문수

전체 Q&A

질문하기