그래프그래프 정의와 용어그래프 G는 공집합이 아닌 정점 집합 V와 간선 집합 E로 구성된다.G = (V,E)두 정점이 간선으로 연결되었다면 두 정점은 인접(adjacent)하다고 한다.자기 자신을 간선으로 연결하는 것을 Self-loop(또는 Self-edge)라고 한다.V(G`)⊆ V(G)이고 E(G`)⊆ E(G)인 그래프 G`를 그래프 G의 부분 그래프(subgraph)라 한다.정점 u부터 정점 v까지의 경로(path)는 정점 순서 u, i1, i2, ..., ik, v를 말한다.한 경로의 길이(length)는 경로 상에 있는 간선의 수이다.경로 상에서 처음과 마지막을 제외한 모든 정점들이 서로 다를 때, 그 경로를 단순 경로(simple path)라 한다.처음과 마지막 정점이 같은 단순 경로를 사이..

https://blog.encrypted.gg/942 [실전 알고리즘] 0x0A강 - DFS드디어 01 02 03 이렇게 숫자를 넘어서 0A강에 도달했습니다. 아직 완결까지는 한참 남았지만 아무튼 힘을 내서 계속 잘 해봅시다. 아, 참고로 저번 단원보다는 내용이 많지 않아서 편한 마음으로blog.encrypted.gg대부분의 내용을 위의 게시물을 참고해 작성한 글이다.DFS의 기본 개념이전 게시물에서 BFS에 대해 알고 있다는 것을 전제로 설명한다. DFS를 사용하면 다차원 배열에서 각 칸을 깊이를 우선으로 방문할 수 있다. 그리고 DFS는 재귀로도 자주 사용되는데, 여기에서는 스택을 사용한 DFS만 설명하겠다. DFS에는 스택이 사용된다. BFS와 유일하게 다른 점은 큐 대신 스택이 사용된다는 것 밖에..