[BFS,DFS] 백준 1260번

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

1260번: DFS와 BFS

 

간단하게 , DFS와, BFS의 동작 방식에 대해서 개념을 잡는 가장 기초적인 예제이다.

우선 최단 경로찾기에 대한 솔루션으로 알고있는 DFS는, 재귀형태로 구현하는 것이다.

즉, 가장 깊이 노드를 탐색하는 것이다. 어떤 노드를 탐색하고, 특정 노드에 대한 다음 탐색노드를 인자로 넣어서 바로 다음 탐색 노드로 함수를 호출하는 형태이다.

 

또, BFS는 탐색 가능한 모든 노드를 우선 큐에 넣고, 해당 하나씩 탐색을 하면서, 다음 순서에 해당 탐색 가능한 것을 넣는 것이다.

 

또한 BFS와 DFS는 중복 간선에 대한 탐색이 벌어질수 있기때문에 항상, 탐색한 노드에 대해서는 체크하는 변수가 있어야 한다.

 

 

간단한 소스 틀이다.

메인에서 변수를 받는 것부터 ~ dfs함수 호출, 초기화, bfs 호출이다. 또한 여기서는 각 받은 변수에 대한 탐색 경로를 한번 정렬해주어야 한다.

 

 

dfs부터 살펴보겠다.

초기 start를 받아서, 해당 start의 배열 인덱스의 값이 미 탐색한 경로라면, 탐색했다고 표시하고 다시 재귀로 굴려준다.

그러면 알아서 탐색 노드 깊이를 깊게 파준다.

 

bfs는, 큐를 사용해서 재귀로 넣지않고, poll과 add를 통해서 넣고 빼면서 체크를 한다.

그리고, 재귀가 아닌, 반복문으로 list의 사이즈를 체크해서 더이상 add된게 없다면 (즉 모든 노드를 탐색해서, 더이상 탐색필요한 노드가 없다면) 종료한다.

 

해당 두가지 방법으로 이 예제를 풀어봤다

기초이긴 해도 아예 오랜만에 처음부터 짜면 조금씩 헷갈려서 시간이 걸린다.

 

1문제 같아도 2문제;;; 양아치;;;