BFS

import java.io.*;
import java.util.*;
 
public class Main {
    static ArrayList<Integer> ad[];
    static boolean[] visit;
    static int nV,nE; //노드, 간선 갯수
    static Queue<Integer> Q;
    static LinkedList<Integer> link;
    public static void main(String []args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        nV = Integer.parseInt(st.nextToken()); //노드 개수
        nE = Integer.parseInt(st.nextToken());
 
        ad = new ArrayList[nV+1];
        visit = new boolean[nV+1];
 
        for(int i = 1; i <= nV; i++)
            ad[i] = new ArrayList<>();
 
        for(int i = 0; i < nE; i++){
            st = new StringTokenizer(br.readLine());
            int t1 = Integer.parseInt(st.nextToken());
            int t2 = Integer.parseInt(st.nextToken());
 
            ad[t1].add(t2);
            ad[t2].add(t1);
        }
        bfs(1);
 
    }
    public static void bfs(int start){
        Q = new LinkedList<Integer>();
        link = new LinkedList<>();
        Q.add(start);
        visit[start] = true;
        while(!Q.isEmpty()){
            int qsize = Q.size();
            System.out.println("=======================");
            for(int i = 0; i < qsize; i++) {
                int element = Q.poll();
                System.out.println(element);
                for (int index : ad[element]) {
                    if (!visit[index]) {
                        Q.add(index);
                        visit[index] = true;
                    }
                }
            }
        }
    }
}
 
8 8
1 2
1 3
2 4
2 5
3 6
3 7
4 8
5 8
=======================
1
=======================
2
3
=======================
4
5
6
7
=======================
8

오늘부터는 bfs에 관한 문제를 풀어볼 것이다. dfs는 깊이에 대해 탐색하는 것이고, bfs는 넓이에 대해 탐색하는 것이다. 

dfs는 stack을 이용하고, bfs는 queue를 이용한다. 그래서 시간 복잡도를 보면 dfs는 O(VE)이고, bfs는 O(V+E)이다. 그래서 같은 문제를 bfs, dfs로 풀면 bfs가 시간이 훨씬 적어진다는 것을 알 수 있다. 그리고 dfs는 컴포넌트의 개수를 구할 수 있었지만, bfs에서는 각 level을 구할 수 있다. 그래서 그 level이 말하는 것은 가장 높이 있는 노드와, 가장 낮은 곳에 있는 노드의 최단 거리를 의미한다. 그래서 얼마만큼 목적 노드에 도달할 수 있는지 알 수 있다.

 

---

2021.08.07

BFS 관련 문제를 풀면, 문제에서 최소 횟수 등 '최소'라는 말이 자주 붙을 때가 있다.

그래서 최소를 구할 때

1. 어느 특정 노드의 최솟값을 구하라고 하거나

2. 아니면 그냥 최소 며칠이 걸리나 

하고 물어보는 경우가 있다.

문제를 풀면서 느낀 것은 1번 같은 경우에는 count배열을 만들어 index가 해당 노드를 나타나게끔 하면 된다.

예로 2644 촌수 계산 문제이다. 원하는 두 노드의 관계를 알기 위해서는 노드를 count배열의 index로 생각하여 count해주면 된다.

 

2번 같은 경우에는 7569 토마토이다. 토마토는 -1을 제외한 모든 행렬들의 value가 1이 될 때까지 걸리는 최소 걸리는 시간이다. 그래서 class 안에 x, y, z, count를 저장하여 제일 큰 count를 출력하면 된다.