[백준 1260번 C++] DFS와 BFS

1260번: DFS와 BFS (acmicpc.net)

1260번: DFS와 BFS

---

 

dfs, 깊이 우선 탐색

 

재귀 또는 스택을 이용해서 구현

 

[출처]  [코딩테스트 대비] DFS, BFS 정리 (tistory.com)

 

루트 노드에서부터 더 이상 내려갈 수 없을 때까지 내려가고, 다음 분기로 넘어가는 탐색 방법

bfs, 너비 우선 탐색 

큐를 이용해서 구현

[코딩테스트 대비] DFS, BFS 정리 (tistory.com)

 

루트 노드에서부터 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동

 

[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS) (tistory.com)

[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)

---

백준 1260 DFS와 BFS c++ (tistory.com)

백준 1260 DFS와 BFS c++

DFS와 BFS 구현을 해봤는데...

예제 1,3은 맞는데, 예제 2에서 BFS가 모두 탐색되지 않는다

출력이 

3 1 2 5 4
3 1 4 

이렇게 나온다

 

[문제의 코드]

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

int n, m, v;
int map[1001][1001]; //인접 행렬 그래프
int visited[1001]; //정점 방문 여부
queue<int> q; 
    
void DFS(int v){
    //현재 노드 방문 
    visited[v] = 1;
    cout << v << " ";
    
    //현재 노드와 인접한 노드를 큐에 넣음
    for(int i=1; i<=n; i++ ){
        if(map[v][i] == 1 && visited[i] == 0){
            DFS(i);
        }
    }
}

void BFS(int v){
    //시작 노드를 큐에 넣음음
    q.push(v);
    visited[v] = 1;
    
    //시작 노드와 인접한 모든 노드를 큐애 넣음음
    while(!q.empty()){
        v = q.front();
        q.pop();
        cout << v << " ";
        
        for(int i=1; i<=n; i++){
            if(map[v][i]==1 && visited[i]==0)
                q.push(i);
                visited[i] = 1;
        }
    }
}

int main()
{
    cin >> n >> m >> v;
    
    for(int i = 1; i <= n; i++) {
        visited[i] = 0;
    }
    
    //인접 행렬 그려주기
    int a, b;
    for(int i=0; i<m; i++){
        cin >> a >> b;
        map[a][b] = 1;
        map[b][a] = 1;
        
    }
    
    DFS(v);
    cout << "\n"; 
    for(int i = 1; i <= n; i++) {
        visited[i] = 0;
    }
 
    BFS(v);
    
    return 0;
}

 

---

문제를 모르겠어서 코드를 찾아봤는데, 아직까지 틀린 부분을 찾지 못했다.

내 눈엔 코드가 똑같은데 두 결과값이 다르게 나온다. 

분명 단순한 문제일 것 같은데 빨리 해결하고 이 글을 끝맺을 수 있길,, 

 

[내 코드]

void BFS(int v){
    //시작 노드를 큐에 넣음음
    q.push(v);
    visited[v] = 1;
    
    //시작 노드와 인접한 모든 노드를 큐애 넣음음
    while(!q.empty()){
        v = q.front();
        q.pop();
        cout << v << " ";
        
        for(int i=1; i<=n; i++){
            if(map[v][i]==1 && visited[i]==0)
                q.push(i);
                visited[i] = 1;
        }
    }
}

[맞는 코드]

void bfs(int v) {
	visited[v] = 1;
	q.push(v);

	while (!q.empty()) {
		v = q.front();
		q.pop();
		cout << v << " ";
		for (int i = 1; i <= n; i++) {
			if (map[v][i]  && !visited[i]) {
				q.push(i);
				visited[i] = 1;
			}
		}
	}
}