깊이우선탐색
-
1260 DFS와 BFS알고리즘/백준 문제 2020. 5. 14. 18:40
입력값 : 4 5 1 1 2 1 3 1 4 2 4 3 4 - DFS (Depth First Search 깊이우선탐색) 한 방향으로 갈 수 있는 끝까지 탐색을 마치고, 그 다음 방향으로 탐색한다. 길이 여러개일 경우 숫자가 작은 정점부터 탐색하므로 1 -> 2 로 이동. 한 방향으로 탐색을 이어가야 하므로 1 -> 2 -> 4 -> 3 으로 이어진다. 마지막 3 에 도착했을 때, 1 과 4는 이미 방문 한 상태이므로 재귀로 호출된 스레드가 하나하나 모두 종료된다. 모든 정점을 방문 했으므로 프로그램은 종료된다. - BFS (Breath First Search 너비우선탐색) 한 정점에 도착했을 때, 그 정점에서 방문 가능한 정점은 모두 방문한다. 동시에 여러 정점을 방문하는 형태이다. 각 정점의 거리가 1일..