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

안녕하세요 360님ㅎㅎ

일단은 이런 상황이죠?

좋은 생각을 하셨네요 ㅎㅎ

이 상황에서는 1번노드부터 탐색하면 가장 많은 노드들을 탐색하는 것을 알 수 있습니다.

제 코드를 실행해보면 1번노드라고 나오며

	for (int i = 1; i <= n; i++) {
		memset(visited, 0, sizeof(visited));
		dp[i] = dfs(i); 
		cout << dp[i] << '\n';
		mx = max(dp[i], mx);
	} 

아래의 dp를 찍어봐도 5라고 나옵니다. 1, 3, 4, 5, 6, 다 탐색을 한 것이죠.

1-3-4-6을 탐색한후 1-3-5-4-6을 탐색하려면 4가 이미 visited로 겹치기에 1-3-5-4-6경로를 탐색을 안하게되는것 아닌가요??

>> 네 그럴수도 있죠. 다만, 1, 3, 4, 6 을 탐색한 이후에 3에서 5를 탐색해서 결국 1, 3, 4, 6, 5 전부 탐색하는 것은 자명하죠? (인접해있는 노드를 다 탐색하니까요) 이 문제는 어떤 순서로 경로를 탐색하는게 중요한게 아니라 1번노드부터 시작해서 해킹할 수 있는 컴퓨터를 모두 탐색하는게 중요하기 때문에 해당 부분은 상관이 없습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI인턴이에요.

kkim360님께서 말씀하신 것과 같은 경우, dfs와 같은 그래프 탐색 알고리즘에서 visited 배열을 활용하지 않는다면 해당 경로를 중복해서 탐색할 가능성이 있습니다. 따라서, visited 배열이 중요한 역할을 하며 방문한 노드를 체크함으로써 중복된 경로를 제외하고 탐색할 수 있도록 도와줍니다.

따라서, 1-3-4-6을 탐색한 후 1-3-5-4-6을 탐색하는 경우 4가 이미 visited로 체크되어 있다면 1-3-5-4-6 경로 탐색을 수행하지 않고, 다른 경로를 탐색할 것입니다. 이와 같이 visited를 활용하면 중복된 경로 탐색을 효율적으로 방지할 수 있습니다.

감사합니다.