[백준 1260] BFS와 DFS

 

 

1. 문제

 

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

2. 핵심 아이디어

 

DFS는 재귀 (Stack)

BFS는 Queue가 비어있을 때 까지.

 

3. 실수

(1) Node별 연결상태를 저장한  vector Array List를

오름차순으로 출력해주기 위해서 

sort 필요

 

(2) Array Index가 0부터인지 1부터 시작인지 체크하기.

(3) 배열 [] 안에 들어가는 변수명 의미를 확실히하기.

 

4. 구현

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
 
bool visited[1001] = {false};
vector<int> v[1001];
 
void DFS(int start){
    //첫 놈은 일단 방문하고 출력 
    visited[start] = true;
    cout << start << ' ';
    
    //인접 노드 갯수만큼 Loop 
    for(int i = 0 ; i < v[start].size(); i++)
    {
        int vertex = v[start][i];
        if(!visited[vertex]) //미방문 노드라면  
        DFS(vertex);
    }
}
 
void BFS(int start){
    visited[start] = true;
    queue<int> q;
    q.push(start);
    
    while(!q.empty())
    {
        int data = q.front();
        q.pop();
        cout << data<< ' ';
        
        for(int i = 0; i < v[data].size(); i++)
        {
            int vertex = v[data][i];
            if(!visited[vertex])
            {
            visited[vertex] = true;
            q.push(vertex);
            }
        }
    }
}
/*
void visitInit(bool visited[])
{
    for(int i = 1; i < sizeof(visited) / sizeof(bool); i++)
    { 
        visited[i] = false;
    }
}
*/
//양방향 Edge 연결 
void addEdge(int start, int end)
{
    v[start].push_back(end);
    v[end].push_back(start);
}
 
int main(void)
{
    int N, M, V; // vertex, Edge, Start Node
    cin >> N >> M >> V;
    int start, end;
    for(int i = 0; i < M; i++) // Connect Edge 
    {
    cin >> start >> end;
    addEdge(start, end);
    }
    // Node 번호 오름차순으로 Array List Sorting 
    for(int i = 1; i <= N ;i++)
    {
    sort(v[i].begin(), v[i].end());
    }
    
    DFS(V);
    cout << '\n';
    for(int i = 1; i < sizeof(visited) / sizeof(bool); i++)
    { 
        visited[i] = false;
    }
    BFS(V);
    
    return 0;     
}

 

 

5. 시간 복잡도

vector (Linked List-based)

O(N + M)

N: Node (vertex) 갯수

M: Edge 갯수

 

BFS의 경우 N + M

DFS의 경우 N + 2M (Connected 왕복)

 

 

6. 부록 (Java, Kotlin)

Java

import java.util.Iterator;
import java.util.LinkedList;


// visited (무한 순환 방지)
// adjacency LinkedList
// queue 에 있는거 무조건 방문 (visited 검사)


public class Graph {
    private int vertexNumber;
    private LinkedList<LinkedList<Integer>> adjacencyList;

    Graph (int vertexNumber) {
        this.vertexNumber = vertexNumber;
        this.adjacencyList = new LinkedList<LinkedList<Integer>>();
        for(int i=0 ; i < vertexNumber ; i++) {
//            Vertex 갯수만큼 List 필요함 (연결된 것들 쭉 순회하기 위해)
            adjacencyList.add(new LinkedList<Integer>());
        }
    }

    void connectEdge(int source, int target) {
        adjacencyList.get(source).add(target);
    }

    void BFS(int target) {
        boolean visited[] = new boolean[vertexNumber];
        LinkedList<Integer> queue = new LinkedList<Integer>();

        visited[target] = true;
        queue.add(target);


//        인접한 애들 모두 Queue 에 추가 (이미 방문한 애들은 제외)
        while (!queue.isEmpty()) {
            int sourceVertex = queue.peek();
            queue.pop();
            System.out.print(sourceVertex + " ");

//            Queue 에 추가.
            Iterator<Integer> itr = adjacencyList.get(sourceVertex).listIterator();
            while (itr.hasNext()) {
                int connectedVertex = itr.next();
                if (!visited[connectedVertex]) {
                    queue.add(connectedVertex);
                    visited[connectedVertex] = true;
                }
            }
        }
    }

}

 

Kotlin

import java.util.*
import kotlin.collections.ArrayList

class GraphK (val vertexNumber : Int){
//    BFS 구현을 위해 중복 방문 방지 visited : BooleanArray
//    adjacencyList

//    인접 리스트들 초기화.
    private val adjacencyArray : Array<ArrayList<Int>> = Array<ArrayList<Int>>(vertexNumber){ ArrayList<Int>() }

    fun connectEdge(source: Int, destination: Int) : Unit {
        adjacencyArray[source].add(destination)
    }

    fun bfs(startVertex: Int) {
        val visited : BooleanArray = BooleanArray(vertexNumber)
        visited[startVertex] = true

        val queue : Queue<Int> = LinkedList<Int>()
        queue.add(startVertex)

        while (queue.isNotEmpty()) {
//          poll : pop and remove!
            val targetVertex = queue.poll()
            print("$targetVertex ")
//            아직 방문하지 않은 노드라면

            adjacencyArray[targetVertex].forEach(){
                if (!visited[it]) {
//                연결된 노드중 미방문 노드 출력함 (BFS 특징)
                    queue.add(it)
                    visited[it] = true
                }
            }

        }
    }

}