코드
#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++) : 코딩테스트 대비' 강의를 수강하며 개인 백업용으로 메모하였습니다.
인프런: //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을 큐에 넣는다.그러면, 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; }