[알골90제] 70번 - 그래프 최단거리 BFS

* 문제 : 1번에서 각 정점으로 가는 최소 간선 수를 2번 정점부터 차례때로 출력하시오

 

- 여기서 dis 배열은 각 정점까지 가는 최소 간선의 수가 저장됨. 3번만에 2번으로 가면, 이미 체크가 되어있어서 4번만에 안감

 

- 1번을 큐에 넣고, 1번만에 갈 수 있는 정점을 찾음 => 3을 체크함 => 3을 큐에 넣고 => dis 배열의 3번 정점의 값을 기록한다 1번정점의 길이와 3번까지 가는 간선수 합해서 입력함 

 

- 1번만에 갈 수 있는건 또 4번 정점 => 4번을 큐에 넣고 4번 dis배열 1 기록

 

// 69번 - 넓이우선탐색 BFS (큐 자료구조 구현)
// 무방향 그래프리스트

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int Q[100], front = -1, back = -1, ch[10];
vector<int> map[10];

int main() {

	int a, b, x;
	
	for (int i = 1; i <= 6; i++) {
		scanf("%d %d", &a, &b);
		map[a].push_back(b); //인접리스트 만듬
		map[b].push_back(a); //무방향이라 이 코드도 추가
	}

	//큐 운영
	Q[++back] = 1; // 큐에 1번 루트 노드 넣기
	ch[1] = 1; // check 배열에 1 넣기
	
	while (front < back) { //같아지는 순간 queue는 비어있다는 것
		x = Q[++front]; //빼는거
		printf("%d", x); //빼고 출력

		for (int i = 0; i < map[x].size(); i++) {
			if (ch[map[x][i]] == 0) {
				ch[map[x][i]] = 1;
				Q[++back] = map[x][i];
			}
		}
	}
	return 0;
}