Root Node 혹은 다른 임의의 노드에서 인접한 노드를 먼저 탐색하는 방법이다.
Queue를 사용해서 구현한다.
접점(V), 간선(E)
class Graph {
private int V;
private LinkedList<Integer> adj[];
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
void addEdge(int v, int w) { adj[v].add(w); }
/* BFS */
void BFS(int s) {
boolean visited[] = new boolean[V];
LinkedList<Integer> queue = new LinkedList<Integer>();
visited[s] = true;
queue.add(s);
while (queue.size() != 0) {
// 방문한 노드를 큐에서 추출(dequeue)하고 값을 출력
s = queue.poll();
System.out.print(s + " ");
// 방문한 노드와 인접한 모든 노드를 가져온다.
Iterator<Integer> i = adj[s].listIterator();
while (i.hasNext()) {
int n = i.next();
// 방문하지 않은 노드면 방문한 것으로 표시하고 큐에 삽입(enqueue)
if (!visited[n]) {
visited[n] = true;
queue.add(n);
}
}
}
}
}
위 문제 모두 BFS 기초적인 문제이다.
BFS를 이용해 해결할 수 있는 문제는 3가지 조건을 만족해야한다.
첫 번째 토마토는 높이는 고려하지 않기 때문에 쉬우나 두번째 토마토 문제는 높이를 고려해야하기 때문에 상당히 까다로워진다.
2019년 라인 하계 인턴문제에 비슷한 유형이 출제되었다.
DP문제로 분류되어 있지만 BFS로 풀 수 있다.
힙 정렬(heap sort), 힙 소트 (0) | 2022.03.19 |
---|---|
DFS (깊이 우선 탐색) (0) | 2022.03.19 |
분할정복(Divide and Conquer) (0) | 2022.03.19 |
완전탐색 (Brute-Force) (0) | 2022.03.19 |
동적 계획법 (DP) 정리 (0) | 2022.03.19 |