[알고리즘] DFS/BFS 활용 ⑥

1. Introduction

1) source

[boj. 1260] DFS와 BFS

2) Overview

• 그래프 정보를 토대로 DFS/BFS 순회 수행 결과를 출력하는 단순한 개념 문제이다.

3) Input & Output

• N과M,V를 입력받은 후 M개의 줄을 반복하여 그래프 정보를 구축한다.

2. Solution I

#include <iostream> // 기본 입출력 라이브러리
#include <vector>	// visited와 graph 구조 저장
#include <algorithm> // graph의 sorting
#include <queue> // BFS queue 활용
using namespace std;

int N,M,Start;
vector<vector<int>> g;
vector<bool> visited;

void DFS(int v)
{
	// *탐색 및 출력
	visited[v]=true;
    cout<<v<<" " ;
    
    // *다음 노드 탐색 (기존 노드-v와 연결된 모든 노드는 탐색 대상이됨)
    for(int next : g[v])
    	if(!visited[next])
        	DFS(next);
}

void BFS(int v)
{
	// *V와 연결된 노드를 차례로 탐색
	queue<int> q;
    q.push(v);
    visited[v] =true;
    
    // *더 이상 연결된 노드가 없을 때까지
    while(!q.empty())
    {
    	// *탐색 및 출력
    	int cur = q.front();
        q.pop();
        cout<<cur<<" ";
        visited[cur] =true;
        for(auto iter = g[cur].begin(); iter!= g[cur].end(); iter++)
        	if(!visited[*iter]) q.push(*iter);
    }
}

int main()
{
	cin>> N>>M>>Start;
    g.resize(N+1);
    visited.resize(N+1,false);
    
    for(int i=0;i<M;i++)
    {
    	int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    
    // *낮은 번호부터 정렬
    for(int i=1;i<=N;i++) sort(g[i].begin(),g[i].end());
	
    // *DFS 및 BFS 순회
    DFS(Start);
	BFS(Start);
    
    return 0;
}

3. Solution II.

@ 오답의 이유
① DFS 이후 개행 출력 및 visited 벡터를 false로 초기화 해주지 않음
ⓑ main 선언 시 return 형 int로 지정 안함
ⓑ BFS 출력 시 visited의 값을 true로 바꿔주는 부분이 for 내부에 있어야만, 중복된 값이 queue에 들어가는 것을 막을 수 있음 ★

#include <iostream> // 기본 입출력 라이브러리
#include <vector>	// visited와 graph 구조 저장
#include <algorithm> // graph의 sorting
#include <queue> // BFS queue 활용
using namespace std;

int N, M, Start;
vector<vector<int>> g;
vector<bool> visited;

void DFS(int v)
{
    // *탐색 및 출력
    visited[v] = true;
    cout << v << " ";

    // *다음 노드 탐색 (기존 노드-v와 연결된 모든 노드는 탐색 대상이됨)
    for (int next : g[v])
        if (!visited[next])
            DFS(next);
}

void BFS(int v)
{
    // *V와 연결된 노드를 차례로 탐색
    queue<int> q;
    q.push(v);
    visited[v] = true;

    // *더 이상 연결된 노드가 없을 때까지
    while (!q.empty())
    {
        // *탐색 및 출력
        int cur = q.front();
        q.pop();
        cout << cur << " ";

        // Solution I. 뭐가 잘못된거지?
        /*     for (auto iter = g[cur].begin(); iter != g[cur].end(); iter++)
            if (!visited[*iter]) q.push(*iter);*/

            // Solution II. 올바른 ver.
        for (int i = 0; i < g[cur].size(); i++)
        {
            if (!visited[g[cur][i]])
            {
                // *중복 삽입을 막고쟈
                visited[g[cur][i]] = true;
                q.push(g[cur][i]);
            }
        }
    }
}

int main()
{
    cin >> N >> M >> Start;
    g.resize(N + 1);
    visited.resize(N + 1, false);

    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    // *낮은 번호부터 정렬
    for (int i = 1; i <= N; i++) sort(g[i].begin(), g[i].end());

    // *DFS 및 BFS 순회
    DFS(Start);
    cout << endl;
    // visited 초기화
    fill(visited.begin(), visited.end(), false);
    BFS(Start);

    return 0;
}