https://novawiki.app/index.php?action=history&feed=atom&title=DFSDFS - 편집 역사2026-04-17T11:48:46Z이 문서의 편집 역사MediaWiki 1.41.1https://novawiki.app/index.php?title=DFS&diff=23010&oldid=prevNovaAdmin: DCWiki 복구: 최신본 이식2026-01-08T08:04:13Z<p>DCWiki 복구: 최신본 이식</p>
<p><b>새 문서</b></p><div>{{공머생}}<br />
Depth First Search, 다른 말로 깊이 우선 탐색이라고 한다.<br />
<br />
그래프가 있으면 방문 안한것들이 보일 때 마다 방문하는거다. [[BFS]]처럼 가까운 거 먼저 탐색하는게 아니라서 깊은 지점에 있는 것을 탐색할때는 유용하다.<br />
<br />
구현할 때 스택 아니면 재귀로 구현하는데 재귀가 훨씬 편하다. <br />
<br />
의사코드로 표현하면 다음과 같다.<br />
<br />
FUNCTION DFS(int src):<br />
Mark src as visited<br />
FOR i in graph[src]:<br />
IF i is not visited:<br />
VISIT i<br />
<br />
C++로 표현하면 다음과 같다.<br />
<br />
void DFS(int src){<br />
Mark src as visited<br />
for(int i = 0;i<graph[src].size();i++){<br />
if(visited[graph[src][i]] == false) DFS(graph[src][i]);<br />
}<br />
}<br />
<br />
그래프 탐색에서는 존나게 중요한 [[알고리즘]] 중 하나로 너비 우선 탐색하고 같이 많이 쓰인다. 보다시피 코드가 짧아서 사실 너비우선탐색보다 구현은 편하다.</div>NovaAdmin