BFS

저번에도 적었지만 코딩하면서 헷갈려서 다시 정리해본다.

BFS가 가능할때

1. 상태(노드)의 수가 적을때 10!이하 3628800

2. 가중치가 1일때, 연산의 비용이 1일때 한칸이동

3. 최소를 구하는 문제 일때

로직은 간단하게

q.push(S);

check[S] = true;

dist[S]  = 0;

while(!q.empty()) {

int temp = q.front();

q.pop();

//어떤연산을 한후

//

//

if(조건) {

if(!check[]){

q.push();

check[] = true;

dist[] = dist[now] +1;

}

}

}

대부분이 이런식이다.

1. 큐에 하나 넣고 넣은 원소를 방문했다고 체크한다. 거리도 0으로 넣어준다.

2. BFS를 큐가 빌 때 까지 반복하는데,

front()에 대해 연산을 수행한다.

연산을 수행한 값이 이미 방문했는지 check한다.

방문했던 거라면 넘어가고 아니라면

check를 true로, dist도 갱신, 그리고 큐에 넣는다.

3. 이를 반복한다.