Sometimes, it is important to make sure that we never visit a node twice. Otherwise, we might get stuck in an infinite loop, e.g. in graph with cycle.
cycle을 가진 graph에서 무한 루프에 빠질 수 있다고 하는데 이걸 벗어나기 위한 방법으로 이 글에서는 set을 하나 만들었는데 다른 방법들도 많이 생각해보면 좋을 것 같다.
There are some cases where one does not need keep the visited hash set:
You are absolutely sure there is no cycle, for example, in tree traversal;
You do want to add the node to the queue multiple times. 이런 경우가 있을까..? 생각 좀 해봐야겠다
BFS by queue process (island & water problem)
-
deque 생성, visited set 생성
-
for 로 grid 돌면서 visited == False인 경우에 BFS 시작
-
처음 시작한 곳이 root node가 되고 상하좌우로(조건문으로 경계에 있는 경우는 또 제외해야함) 인접한 노드가 연결된 노드가 됨
-
if 연결된 노드의 visited == False인 경우에 enqueue
-
enqueue 가 끝난 후