(가설..) BFS - deque 일 경우와 heapq 일 경우

# 1. 만약 q 가 deque 일 경우

# 만약 q가 deque 일 경우

<q, visited 에 시작점 추가>
while q:
    <pop>
    < || 원하는 로직 작성 || >
    <for  다음으로 이동할 수 있는 것들>
        <if -- not visited>
            <q에 추가>
            <방문 처리>

 

q 가 일반 큐일 경우, 시작점을 q와 visited에 먼저 채워 넣는다. 

 

while문을 시작하고, for 문 전까지 원하는 로직만 작성한다. 

다음으로 이동할 수 있는 칸에 대하여 for문을 수행하는데, 이 때는 방문하지 않은 점들만 탐색하고, 

q에 추가하자마자 방문 처리를 해준다. 

 

이는 가중치는 없고 오로지 먼저 도착하면 장땡인 문제에 적용된다. 

 

# 2. 만약 q가 heapq 일 경우

# 만약 q가 heapq일 경우

<heapq에 시작점 추가, visited 는 빈 상태>
while q:
    <pop>
    <if -- visited : continue>
    <방문처리>
    < || 원하는 로직 작성 || >
    <for  다음으로 이동할 수 있는 것들>
        <heapq 에 추가>

 

먼저 도착한다고 되는게 아니라, 가중치가 있어서 이에 따른 우선순위가 존재할 때 적용할 수 있는 문제다. 

일반 큐를 쓰지 않고, 우선순위 큐인 heapq 를 사용한다. 

 

먼저 heapq에 시작점을 추가하는데, visited는 아직 넣지 않고 놔둔다. 방문처리는 while문에서 할 것이다. 

while 문을 실행하고, 여느떄와 같이 가장 먼저 해야할 것은 pop.

pop을 하고 나서, 방문 여부를 확인한다. 방문 처리를 뒤에 q에 넣자마자 하는 것이 아니라, 꺼낸 다음에 방문 처리를 하기 때문에, 꺼내고 나서 방문 여부를 확인해야 한다. 

꺼내자마자 방문 여부를 확인하고, 방문했으면 패스. 방문하지 않았으면 즉시 방문처리를 하고 원하는 로직을 실행한다. 

 

그리고 도달할 수 있는 점들에 대해 for문을 수행하는데, 안에서 해줄 것은 heapq에 추가하는 것 외엔 없다. 

위에서 언급했듯이 먼저 도착하면 장땡인게 아니라, 일단 싹다 후보지에 넣고 우선순위에 따라 고르는 것이기 때문에, 큐에 일단 무지성으로 집어넣는다. 

 

 

---

이 가설이 맞을까?