너비 우선 탐색 BFS

백준 1260
백준 12851

너비 우선 탐색 BFS

: 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색.

기능 : 그래프 완전 탐색
시간복잡도 : O(Node+Edge)
자료구조 : FIFO, 큐(queue)

DFS vs BFS

DFS : 그래프의 모든 경로를 탐색, 백트래킹, 순열/조합, 종료 조건 명확
BFS : 가중치가 없는 그래프의 최단 경로, 최소 비용, 레벨 별로 탐색

BFS 로직

• 노드 방문 여부를 체크할 배열 visited 필요
• 그래프는 인접 리스트로 표현
• 큐(dfs와 차이)

1. 그래프를 인접 리스트로 표현, 방문 배열 초기화
2. 큐에 시작노드 추가
3. 큐에서 노드를 꺼내고 꺼낸 노드의 인접 노드를 다시 큐에 삽입
4. 큐가 빌 때까지 2 반복

중요한 점

1. 중복 방문 체크는 반드시 큐에 넣기 전에 해야 한다. 다른 노드가 큐에 중복으로 넣는 것을 방지하기 위해서
2. 만약 bfs에서도 dfs처럼 depth를 기록하고 싶다면, 배열을 만들어서
   depth[next] = depth[current] + 1; 이렇게 기록한다. 단, 여기서도 1번과 같이 큐에 넣기전에 해야 한다.

백준 1260

import java.util.*;

public class Main {

	static boolean[] visited;
	static ArrayList<ArrayList<Integer>> graph;
	static int[] parent;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int V = sc.nextInt();
		int E = sc.nextInt();
		int start = sc.nextInt();
		
		// 인접 리스트
		graph = new ArrayList<>();

		// 초기화
		for (int i = 0; i < V + 1; i++) {
			graph.add(new ArrayList<>());
		}

		int x, y;
		for (int i = 0; i < E; i++) {
			x = sc.nextInt();
			y = sc.nextInt();
			// 양방향
			graph.get(x).add(y);
			graph.get(y).add(x);
		}
		
		//정렬
		for (int i = 0; i < V + 1; i++) {
			Collections.sort(graph.get(i));
		}

		// 방문한 노드 배열
		visited = new boolean[V + 1];
		
		dfs(start,0);
		System.out.println();
		
		for (int i = 0; i < V + 1;i++) {
			visited[i] = false;
		}
		bfs(start);
		
		sc.close();

	}

	public static void dfs(int now, int depth) {
		visited[now] = true;
		System.out.print(now + " ");
		
		for (int next : graph.get(now)) {
			if (!visited[next]) {
				dfs(next, depth + 1);
			}
		}
		//visited[now] = false;

	}
	
	
	public static void bfs(int start) {
		Queue<Integer> queue = new LinkedList<>();
		
		queue.add(start);
		visited[start] = true;
		
		while (!queue.isEmpty()) {
			int node = queue.poll();
			System.out.print(node + " ");
			
			for (int next : graph.get(node)) {
				if (!visited[next]) {
					queue.add(next);
					// 같은 값을 여러번 큐에 넣지 않기 위해
					visited[next] = true;
				}
			}
		}
	}

}

백준 12851(최단 시간으로 가는 모든 경로)

import java.util.*;

public class Main {

	static int N, K, min, cnt;
	// 중복 방문을 허용 1*2=2, 1+1=2
	// static boolean[] visited;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		K = sc.nextInt();

		if (N == K) {
			System.out.println("0\n1");
		} else {
			min = Integer.MAX_VALUE;
			cnt = 0;
			bfs(N);

			System.out.println(min + "\n" + cnt);
		}
		sc.close();

	}

	public static void bfs(int start) {
		Queue<Integer> queue = new LinkedList<>();

		queue.add(start);

		// bfs는 같은 레벨을 동시에 방문하므로 int형이 아니라 int[]로
		// 경로 별로 방문 번호가 다르게 저장되어야 함.
		int[] count = new int[100001];

		while (!queue.isEmpty()) {
			int node = queue.poll();

			if (min < count[node]) {
				return;
			}

			for (int i = 0; i < 3; i++) {
				int next = node;
				switch (i) {
				case 0:
					next = node - 1;
					break;
				case 1:
					next = node + 1;
					break;
				case 2:
					next = node * 2;
					break;
				}

				if (next == K) {
					if (count[node] + 1 < min) {
						// 새로운 최단경로
						min = count[node] + 1;
						cnt = 1;
					} else if (count[node] + 1 == min) {
						cnt++;
					}
				}

				if (next <= 100000 && next >= 0) {
					// 방문 번호 저장
					// (첫 방문, 같은 장소를 같거나 더 빠르게 방문)
					if (count[next] == 0 || count[next] >= count[node] + 1) {
						queue.add(next);
						count[next] = count[node] + 1;
					}
				}

			}
		}
	}

}