2-P DFS 코드 질문 드립니다

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

2-P

해결된 질문

작성

안녕하세요, 강사님.

강의 보기 먼저 혼자서 고민하며 풀어보았는데요,

https://www.acmicpc.net/source/share/46676449a9414be689433f27149f744b

바이러스를 확산시킬 때 이번 문제의 경우 방문한곳을 굳이 체크하지 않고 값이 0인 지점은 모두 확산하면 되겠다고 생각해서 visited 배열 사용하여 이미 방문한 노드에 대한 확인은 하지 않았는데요, 이렇게 풀어도 괜찮은게 맞을까요?

백준 제출 시 정답이 나오긴 했는데 찝찝해서 질문드립니다.

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 ㅎㅎ

void combi(int start, vector<pair<int,int>> &b)
{
	if(b.size()==3)
	{
		int a_copy[12][12];
		memcpy(a_copy,a,sizeof(a));
		for(auto it : b)
		{
			int y = it.first;
			int x = it.second;
			a_copy[it.first][it.second] = 1;
		}

앞의 코드처럼 매 경우의 수마다 새로이 배열을 만들어서 -> a ->a_copy를 기반으로 했기 때문에 괜찮습니다.

visited 배열을 사용하지 않아도 저렇게 하신다면 괜찮은 로직입니다. 잘 하셨습니다.

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

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

감사합니다.

강사 큰돌 올림.

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다. HyundaiCanI?님.

질문해주신 DFS 관련 문제는 방문한 노드를 확인하는 방법에 대한 고민이시군요. 바이러스 확산 문제를 해결하실 때, visited 배열을 생략하고 문제를 해결하셨다고 하셨습니다. 이 방법에도 특정 조건에서는 올바르게 작동할 수 있지만, 몇 가지 주의할 점이 있습니다.

메모리 및 성능 이슈: 방문 체크를 위한 추가적인 배열을 사용하지 않으면 메모리 사용량은 줄어들 수 있습니다. 하지만, 모든 0인 지점을 다시 방문할 수도 있으므로, 큰 입력 데이터에서는 비효율적일 수 있습니다.
코드의 명확성 및 유지보수성: 협업 환경이나 장기적인 유지보수를 고려한다면, 직관적인 visited 배열을 사용함으로써 누가 방문했는지 명확히 알 수 있어 가독성이 증가합니다. 나중에 기능을 수정하거나 추가할 때도 더 쉽게 대응할 수 있습니다.
경우의 수 누락 가능성: 특정 경우, 0의 상태가동시에 다른 상태로 바뀌면서 충돌이 발생할 수 있습니다. 예를 들어, 처리 순서에 따라 결과가 다르게 나오는 경우도 있습니다.

기본적으로 문제를 정확히 풀었다고 해도 이러한 점들 때문에 일반적인 알고리즘 구현에서는 visited 체크를 선호합니다. 그래도 문제가 정답 판정을 받은 것을 보니, 특정 조건에서는 문제가 없었다고 할 수 있겠습니다.

유사한 질문들과 답변을 찾아보니 다음 링크들이 도움이 될 수 있습니다:

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.

현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

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

2-P DFS 코드 질문 드립니다