그래프 최단거리(BFS) / c & c++ / 제한시간 없음

▣ 문제

다음 그래프에서 1번 정점에서 각 정점으로 가는 최소 이동 간선수를 출력하세요.

▣ 입력설명

- 첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연 결정보가 주어진다.

 

▣ 출력설명

- 1번 정점에서 각 정점으로 가는 최소 간선수를 2번 정점부터 차례대로 출력하세요.

 

▣ 입력 예시

6 9 1 3 1 4 2 1 2 5 3 4 4 5 4 6 6 2 6 5

 

▣ 출력 예시

2 : 3 3 : 1 4 : 1 5 : 2 6: 2

 

<코드> - c

#pragma warning(disable:4996)
#include<stdio.h>
#include<stdbool.h>

int queue[1000];
int visit[21] = { 0 };
int graph[21][21] = { 0 };
int cnt[21] = { 0 };
int front = 0, rear = 0, n;
bool flag = false;

void bfs(int vertex) {
	int num = 1;
	visit[vertex] = 1;
	queue[rear++] = vertex;
	while (front < rear) {
		int v;
		v = queue[front++];
		for (int i = 1; i <= n; i++) {
			if (graph[v][i] == 1 && visit[i] == 0) {
				visit[i] = 1;
				queue[rear++] = i;
				cnt[i] = num;
				flag = true;
			}
		}
		if (flag == true) num++;
		flag = false;
	}
}


int main() {
	int m, i, a, b;
	scanf("%d %d", &n, &m);
	for (i = 0; i < m; i++) {
		scanf("%d %d", &a, &b);
		graph[a][b] = 1;
	}
	bfs(1);

	for (i = 2; i <= n; i++) {
		printf("%d : %d\n", i, cnt[i]);
	}

	return 0;
}

c언어 만들기 더 편한 인접행렬로 코드를 짯다.

 

BFS함수에서 큐(Queue)가 비어있을떄까지  while문을 진행한다. 큐 맨 앞에 저장되어있는 데이터를 불러온후 해당 행렬의 그래프를 탐색했다. 만약 graph[ ][ ] 가 '1'이고 방문하지 않았다면 큐에 저장하고 visit을 표시한다.

 

이때 flag라는 bool변수는 최소 간선수를 구하기 위해 설정해두었다. 만약 탐색을 하는 정점에서 다른 정점으로 갈 수 있다면 이동 간선수가 증가하게 되므로 'flag=true'를 해준다. for문이 끝난후 enqueue가 하나라도 되어있다면 이동 간선수가 증가 했다는 뜻이므로 'num++'를 해주었다.

 

예를 들면, 시작 부분인 '1'은 '3'과 '4'를 enqueue해준다. 이는 3번, 4번 정점으로 이동 간선수가 1이라는 뜻이다. '3'은 이동 할수 있는 정점이 없고 '4'의 경우 '5'와 '6'을 enqueue해주는데 이는 5번, 6번 정점으로 가기 위해서는 이동 간선수가 2가 필요하다.

 

그리고 마지막에는 항상 'flag=false'라고 다시 초기화 시켜준다.

 

 

<코드> - c++

#pragma warning(disable:4996)
#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int dis[21];
int visit[21] = { 0 };

int main() {
	int n, m, i, a, b, x;
	vector<int> map[21];
	queue<int> Q;
	scanf("%d %d", &n, &m);
	for (i = 0; i < m; i++) {
		scanf("%d %d", &a, &b);
		map[a].push_back(b);
	}
	Q.push(1);
	visit[1] = 1;
	while (!Q.empty()) {
		x = Q.front();
		Q.pop();
		for (i = 0; i < map[x].size(); i++) {
			if (visit[map[x][i]] == 0) {
				visit[map[x][i]] = 1;
				Q.push(map[x][i]);
				dis[map[x][i]] = dis[x] + 1;
			}
		}
	}
	for (i = 2; i <= n; i++) {
		printf("%d : %d\n", i, dis[i]);
	}

	return 0;
}

c++에서는 vector를 이용해 인접리스트를 사용했다.

 

위의 코드와 진행은 동일하다.

 

int dis[21]은 각 정점의 이동 간선수를 저장하는 배열이다. dequeue를 하면서 while문 안의 if(visit[ ] == 0) 이 성립되면 dis[ ]를 누적합 해주는 방식으로 답을 구한다.