[백준(BOJ)/C++] 1260번: DFS와 BFS - 코딩밥상

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

1260번: DFS와 BFS

 

• 접근 방법, 논리 흐름(알고리즘)

정점과 간선의 갯수와 시작하는 지점까지 알려주는 친절한 문제이다. 기본적인 DFS와 BFS의 개념을 물어보는 기본 문제인데, 이 문제를 통해 알고는 있었지만 헷갈리던 개념들과 동작원리를 좀 더 세세하게 익힐 수 있었다.



우선 수업에서 입력받는 값들을 보면 헷갈릴거라고 하셨는데 문제를 접하고 나서야 그게 무슨 의미인가 알 수 있었다. 서로 간선으로 이어져있는 정점 쌍이 주어지는데, 수업에 들었던 조언과 같이 헷갈리지 말고 그냥 각 정점의 벡터에 저장하기로 했다.

그 후 문제 조건에서 수가 작을수록 탐색을 빠르게 하기위해 sort처리를 해 주고 코드를 짰다.

 

 

먼저 DFS 코드를 보면, 방문 처리를 해주어 무한 루프에 빠지지 않고 각 정점과 이어져있는 정점을 방문하여 모든 정점들을 들리는데, 

여기서 내가 이해한 가장 중요한 원리는 LIFO이다.

학교 자료구조 수업시간에 배웠듯이, dfs는 stack으로 구현 가능하다. 다음으로 방문 할 곳은 방문 하지 않은 연결된 다음 노드이고 이 노드는 출력 후 먼저 스택에 저장된다.  이는 재귀함수로 구현 가능하다 재귀 함수 또한 리턴이 걸리면 LIFO처럼 그 전 재귀 함수로 돌아가기 때문이다. 즉 노드의 깊이를 따라 방문하게된다.

 

 

다음으로 BFS를 보면 큐에 노드들을 저장하는데, FIFO을 활용하는것을 생각하면 이해가 쉽다.

연결된 노드(자식 노드)들을 큐에 저장하고 또 그 노드들의 자식 노드들을 그 뒤에 저장한다. 

이렇게되면 그 자식 노드들끼리 층을 만들어 저장하는것처럼 된다.

즉 넓이 우선 탐색이 된다.