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
이전 DFS와 BFS포스팅에서는 양방향 그래프가 아니었기 때문에 노드 연결관계를 입력값으로 넣을 때 간선이 시작하는 노드의 인덱스에 간선이 도착하는 노드의 정보를 담아 그래프를 탐색했었다.
해당 알고리즘 문제에선 양방향 그래프를 구현하는 것이 주요 포인트였다. 양방향 그래프는 그래프 노드들의 인덱스 내에서 서로 연결되어 있는 노드의 인덱스에 1을 넣음으로써 노드들이 서로 연결되어있음을 표현했다.
즉 위의 그림처럼 노드1에 노드 2와 3이 연결되어있으면 행렬의 1행 2열과 3열에 1을 넣고, 마찬가지로 2행 1열과 3행 1열에도 1을 넣음으로써 양방향 관계를 표현했다.
이후 dfs, bfs알고리즘 구현은 이전과 비슷하나 다른 그래프로 옮겨가는 조건문에서 '방문하지 않은 노드'조건문에 추가로 '해당 노드가 서로 연결되어 있는지 연결성'을 확인하는 조건문도 필요하다.
'python > 알고리즘 문제풀이' 카테고리의 다른 글
| [백준 | 파이썬3] 10828. 스택 (2) | 2021.07.26 |
|---|---|
| 위상정렬 (1) | 2021.07.23 |
| [백준 | 파이썬3] 11279. 최대 힙 (0) | 2021.07.22 |
| [백준 | 파이썬3] 1753. 최단경로- 다익스트라/ 런타임에러 input() vs stdin.readline (2) | 2021.07.18 |
| 최소신장트리, 크루스칼 알고리즘 (1) | 2021.07.16 |