BFS

BFS

너비우선 탐색

너비우선 탐색은 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 중 하나이다. 현재 정점과 인접한 정점을 검사하다가 방문하지 않은 정점을 발견하면 큐에 넣는다. 큐에 차례대로 넣은 노드 순서로 방문하는 방식이다.

---

“개쉽네 ㄹㅇㅋㅋ”

실제로도 원리는 쉽다. 탐색과정을 보자.

boolean[] visit   //방문 여부 체크 배열
Queue<Integer> que   //방문할 노드 저장

1. 시작 노드를 큐에 추가하고, 방문여부 visit=true로 지정한다.
2. 해당 노드 근처에 연결된 노드들 중 방문하지 않은 노드를 방문체크하고, 방문할 리스트 저장한다.
3. 더이상 탐색할 노드가 없을 때까지 방문할 리스트(큐)에 노드가 없을 때 = que.isEmpty 까지 방문 로직을 반복한다.

---

방문여부 실제로 방문하기 전에 체크하는 이유는 방문할 리스트(큐)에 넣을 때 중복해서 추가하는 경우를 방지하기 위해서이다. 체크를 먼저하지 않으면, 방문했던 노드를 다시 방문하는 경우가 있기 때문이다.(A→B로 탐색했는데, 체크가 안 되었기 때문에 B→A로 다시 방문하게 됨.) 따라서 방문하는 경우 해당 노드를 큐에 넣을 때 방문 여부를 체크한다.

즉, 다음과 같은 그래프가 있을 때 근처에 연결된 노드들 전부를 돌고, 그 다음 노드들 순으로 탐색하는 방식이다.

즉, 이 그래프를 A노드를 시작으로 BFS 방식으로 탐색하면 다음과 같다. A-B-C-D-E-F-G

과정은 다음과 같다.

시작 노드 A를 방문했다는 것을 체크(true)로 하고 A와 연결된 노드를 보니, B, C, D가 연결되어있다. 순서대로, B,C,D를 큐에 넣고, 각 방문 여부를 체크한다.

이후 큐에서 하나씩 노드를 꺼낸다. 이때 B를 먼저 넣었기 때문에, B노드 근처의 노드를 탐색하게 된다.

방문하지 않은 노드중 B와 연결 된 노드는 E로 해당 E를 큐에 넣고, 방문체크한다. 이후 큐에서 다시꺼내면, C부터…. 그다음 D.. 이를 반복한다.

JAVA

---

...
//visit[]은 방문 여부
//edge[][]은 근접한 노드 여부

public static void BFS(int cur) {
	Queue<Integer> que = new LinkedList<Integer>();
	visit[cur] = true;
	que.add(cur);

	while(!que.isEmpty()) {
		int t = que.poll();

		for(int i=0; i<N; i++) {
			if(visit[i] || !edge[cur][i]) continue;
			visit[i] = true;
			que.add(i);
		}
	}
}

추천문제

---

1260번: DFS와 BFS