C 언어 BFS 최단거리 - C eon-eo BFS choedangeoli

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int ch[21], dis[21];

int main(void)
{
	int n, m, i, a, b, x;
	vector<int> map[21];
	queue<int> Q;

	cin >> n >> m;

	for (i = 1; i <= m; ++i)
	{
		cin >> a >> b;
		map[a].push_back(b);
		map[b].push_back(a);
	}

	Q.push(1);
	ch[1] = 1;

	while (!Q.empty())
	{
		x = Q.front();
		Q.pop();

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

	for (i = 2; i <= n; ++i)
	{
		cout << i << " : " << dis[i] << endl;
	}

	return 0;
}

출력 결과

해당 포스트는 'it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비' 강의를 수강하며 개인 백업용으로 메모하였습니다.

인프런: https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#

it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 - 인프런

알고리즘과 자료구조를 이용해 문제해결력을 기르는게 주 목적입니다. 초급 취업 ・ 이직 프로그래밍 언어 알고리즘 C++ 알고리즘 코딩 테스트 개발자취업 온라인 강의 알고리즘

www.inflearn.com

신규 블로그를 만들었습니다!

BFS 너비 우선 탐색

탐색을 할때 너비를 우선으로 탐색하는 알고리즘

BFS 탐색 알고리즘을 통해 '최단 경로'를 찾을 수 있다.

응용하면 미로찾기와 같은 알고리즘도 구현할 수 있다.

BFS를 구현하기 위해 큐(Queue)를 사용한다.

그러면, 1 2 3 4 5 6 7 8 9 순으로 탐색이 완료된다.

코드 구현

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int number = 9;
int visit[9];
vector<int> a[10];

void bfs(int start){
    queue<int> q;
    q.push(start);
    visit[start] = true;
    
    while(!q.empty()){
        // 큐에 값이 있을경우 계속 반복 실행
        // 큐에 값이 있다. => 아직 방문하지 않은 노드가 존재 한다. 
        int x = q.front();
        q.pop();
        printf("%d ", x);
        for(int i=0; i< a[x].size(); i++){
            int y = a[x][i];
            if(!visit[y]){
                // 방문하지 않았다면..
                q.push(y);
                visit[y] = true; 
            }
        }
    }
}

int main(void){
    
    // 1과 2를 연결 
    a[1].push_back(2);
    a[2].push_back(1);
    
    // 1과 3을 연결 
    a[1].push_back(3);
    a[3].push_back(1);
    
    // 2와 4를 연결 
    a[2].push_back(4);
    a[4].push_back(2);

    // 2와 5를 연결 
    a[2].push_back(5);
    a[5].push_back(2);
    
    // 4와 8을 연결 
    a[4].push_back(8);
    a[8].push_back(4);
    
    // 5와 9를 연결 
    a[5].push_back(9);
    a[9].push_back(5);
    
    // 3과 6을 연결 
    a[3].push_back(6);
    a[6].push_back(3);
    
    // 3과 7을 연결 
    a[3].push_back(7);
    a[7].push_back(3);
    
    // 1번 노드부터 bfs 탐색 실행 
    bfs(1);
    
    return 0;
} 
​