[Python] BOJ(백준) 1260번 - DFS와 BFS

링크

https://www.acmicpc.net/problem/1260

난이도(solved.ac 참고)

실버2

풀이

걍 뭐.. 설명할 것도 없다. 이거 못풀면 다른 모든 그래프 탐색 문제도 못 푼다..

일반적인 DFS와 BFS 구현에서 아주 살짝 달랐던 점은, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다는 점이다. 이 부분은, v 지점을 방문 표시한 뒤에 인접 리스트의 인덱스 v를 기준으로 연결된 여러 정점 중 가장 작은 것부터 방문해야 된다는 뜻이다. 따라서, graph에 대한 for문을 돌 때 sorted() 처리를 해주면 된다.

 

아 그리고, 인접 리스트의 총 길이는 n과 m 중 큰 값 + 1만큼 되어야 한다는 점도 고려해야 한다.

예를 들어 정점은 1000개지만 간선은 1개일 때나, 정점은 5개지만 간선이 6개일 때를 생각해보면 n이나 m 중 어느 한 값으로 고정시킬수는 없다는 것을 알게 될 것이다.