-
질문 & 답변
카테고리
-
세부 분야
게임 프로그래밍
-
해결 여부
미해결
Dfs 함수의 순방향 간선 예외 체크 로직에 대해 여쭤봅니다.
23.09.17 16:28 작성 조회수 206
0
Dfs 함수에서
if(_discoveredOrder[here] < _discoveredOrder[there]) contiue;
해당 로직을 통해서 순방향 간선이면 continue를 하여 넘어갔는데 해당 if 문에 걸리는 경우가 존재하나요??
_discoveredOrder[there]의 값이 -1이 아니라는 뜻은 자신의 부모로부터 이미 방문한 적이 있다는 뜻인데 if 문에 걸리는 것이 없는 것 같아서요.
어떤 경우에 발생하는 지 궁금합니다.
답변을 작성해보세요.
0
인프런 AI 인턴
2023.09.19
안녕하세요, 인프런 AI 인턴이에요.
if(_discoveredOrder[here] < _discoveredOrder[there]) continue; 해당 로직은 DFS(Depth-First Search) 알고리즘에서 순방향 간선을 처리하기 위한 예외 체크 로직입니다.
여기서 _discoveredOrder[here]는 현재 정점(here)의 방문 순서, _discoveredOrder[there]는 순방향 간선으로 연결된 정점(there)의 방문 순서를 나타냅니다.
_discoveredOrder 배열은 초기 값이 -1로 설정되어 있으면서, 각 정점이 방문되는 순서대로 값이 갱신됩니다. 따라서 _discoveredOrder[there] 값이 -1이 아니라는 것은 정점 there이 이미 방문되었다는 의미입니다.
순방향 간선은 정점 here에서 정점 there으로 이어지는 간선이지만, 정점 there이 이미 방문된 상태라면 이 간선은 순환 구조를 형성하게 되며, 따라서 이 간선은 무시해야 합니다. 그래서 if(_discoveredOrder[here] < _discoveredOrder[there]) continue; 코드에서는 이러한 순환 구조를 방지하기 위해 continue 문을 사용하여 다음 간선으로 넘어가도록 처리하고 있습니다.
따라서, 순방향 간선인데 해당 if 문에 걸리는 경우는 발생하지 않으며, 이 경우에는 continue 문을 실행하지 않습니다.
더 자세한 내용이나 다른 질문이 있다면 언제든지 물어보세요. 좋은 하루 되세요!
답변 1