Graph2 Graph에 대해서 그래프는 알고리즘에서 자주 나오고 또 중요한 자료구조입니다.최단거리를 찾는 다익스트라 알고리즘이나 특정 지점을 탐색하는 DFS, BFS가 대표적입니다. 서론은 짧게 하고, 본론으로 들어가겠습니다. Graph란 무엇인가?그래프는 정점과 간선로 이루어진 구조라고 할 수 있습니다.여기서 정점은 보통 node, vertex라고 부르며 간선은 edge라고 부릅니다.*주의할 점 : 간선이 존재하지 않으면 그래프가 아닙니다. 그래프를 시각적으로 보자면 이렇습니다. A, B, C라는 3개의 노드와 3개의 간선으로 이루어진 간단한 그래프입니다.후에 설명드릴 내용으로 조금 더 자세히 설명해 드리자면 이 그래프는 무방향 그래프로 방향성이 존재하지 않는 그래프입니다. 바로 다음으로 넘어가도 되지만 그래프의 잘못된 예도 .. 2025. 3. 23. DFS (Depth First Search) 깊이 우선 탐색 설명 DFS는 우선 제목에 나와있듯이 '탐색'하는 알고리즘입니다.고로 이는 순서가 있는 혹은 방향이 있는 자료구조에서 쓰이며이는 선형 자료구조라고 합니다. 우선 DFS의 탐색 과정을 봅시다.위의 사진은 DFS의 작동 순서를 매우 간단히 표현한 그래프입니다.화살표를 신경쓰기보다는 노드의 숫자를 보시면 좋습니다.노드의 숫자는 순서를 의미합니다. 고로 DFS의 원리를 정리하자면연결된 노드들 중 하나를 골라 그 노드에서 계속 탐색하고 탐색되지 않은 노드는 따로 처리하는 것입니다. 이를 코드로 구현하면 아래처럼 됩니다.*코드에서는 연결요소(connected component)를 구합니다.주석 On, m = map(int ,input().split()) # n : node, m = 간선visited = []graph =.. 2024. 11. 2. 이전 1 다음
