백준 알고리즘을 푸는 도중 알게된 지식을 기재하였습니다.
https://www.acmicpc.net/problem/1260
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
DFS와 BFS 문제를 접하게 되면, 흔하게 나오는 단어들이 있습니다.
- 노드 (Node) / 정점(vertex)
→ 그래프에서의 특정 위치나 개체를 나타내는 단위입니다. - 간선 (Edge)
→ 그래프에서 노드 간의 관계를 나타내는 선입니다.
→ 정점을 연결하며, 방향성과 가중치 등의 속성을 가질 수 있습니다.
이 노드들의 간선 관계를 표시하는 방법 중 하나가 인접행렬입니다.
인접행렬 그래프를 표시하는 것에는 방향그래프인지, 무방향그래프인지에 따라서 달라집니다.
① 무방향 그래프
· 임의의 한 정점에서 자기 자신을 가리키는 간선은 없기 때문에 인접 행렬의 대각선은 항상 0입니다.
· 간선 (Vi, Vj)는 간선 (Vj, Vi)와 같은 의미이기 때문에 행렬의 (i, j)값과 (j, i)값은 항상 같습니다. 따라서 무방향 그래프에서 인접 행렬은 대각선을 기준으로 대칭을 이룹니다.
· 행 i의 합은 열 i의 합과 같고 정점 i의 차수가 됩니다.
② 방향 그래프
· 임의의 한 정점에서 자기 자신을 가리키는 간선은 없기 때문에 인접 행렬의 대각선은 항상 0입니다.
· 간선 <Vi, Vj>는 간선 <Vj, Vi>와 다르기 때문에 행렬의 (i, j)값과 (j, i)값은 다릅니다. 따라서 방향 그래프에서 인접 행렬은 대각선을 기준으로 대칭을 이루지 않습니다.
· 방향 그래프에 대한 인접행렬에서 행 i의 합은 정점 i의 진출차수가 되고, 열 i의 합은 정점 i의 진입차수가 됩니다.
이러한 개념들을 이용하여 입력받은 그래프의 간선 관계를 인접 행렬로 표시하고, DFS와 BFS 알고리즘을 구현하여 그래프를 탐색할 수 있습니다.
이를 통해 그래프 구조에서 노드와 간선의 관계를 이해하고, 다양한 문제를 해결할 수 있습니다.