탐색 알고리즘 정리 (DFS vs. BFS)

논리 흐름
seen : 스택공간과 중복처리를 방지하기 위해 필요한 hashSet이라고 가정

1. DFS

풀이:
'a'를 기준점으로 삼아 스택에 'a'를 추가합니다. 그리고 'a'를 이미 처리했음을 나타내기 위해 해시셋에 'a'를 추가합니다.
'a'를 처리하기 위해서는 인접한 정점인 'b', 'c', 'd'가 후보가 되며, 이들을 스택에 추가합니다.
이후 'b', 'c', 'd'를 처리하기 위해서는 각각의 인접 정점을 고려해야 하므로 이에 대한 처리가 필요합니다. 결국 스택은 모든 요소가 pop되어 비게 되고, seen에는 'a', 'b', 'e', 'g', 'c', 'f', 'd'가 모두 포함됩니다.
이는 'a'를 기준으로 가장 먼 정점부터 차례대로 스택에 담기는 과정을 의미합니다.

2. BFS

이번엔 스택이 아닌 queue를 사용하게됩니다.

• queue는 FIFO규칙을 따릅니다

결과적으로는 a b c d e f g 가 되는데 그림으로 그려보면

이렇게 되는 겁니다.

BFS를 통해서 풀수 있습니다. 먼저 들어간 방 0번에 1,3번방 키를 가지고 있는데 결론적으로 모든 방을 순회하는 과정에서 pop을 통해 해쉬셋에 선입선출로 값이 저장되고 그 결과 모든 방을 순회할수 있게됩니다.