[c++] 1260번: DFS와 BFS

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

1260번: DFS와 BFS

 

문제 요약

 

DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램 작성하기

방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것을 먼저 방문하고 더이상 방문할 수 있는 점이 없으면 종료한다.

정점 번호는 1~N

 

범위

 

정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000)

 

 

---

 

 

그래프를 다시 공부하면서 풀었던 문제 (vector로 구현)

간단하게 정리해보자면

 

DFS (Depth First Search) : 깊이 우선 탐색

 

끝까지 내려갔다가 다음 가지로 넘어가는 형식. 해당 가지를 모두 탐색하는 방법

(끝까지 내려가므로 구해진 답이 최적의 답이 아닐 수 있다.)

 

1. 탐색 시작 노드부터 방문 처리하면서 시작
2. 해당 노드의 인접 노드를 차례대로 방문해서
   • 해당 원소가 방문 안한 노드라면, 그 노드의 인접노드를 찾아서 들어간다(재귀함수)
   • 해당 원소가 방문한 노드라면 넘어간다.

 

🚨 노드 방문시 방문 여부를 반드시 체크해줘야 한다.

 

 

 

BFS ( Breadth First Search) : 너비 우선 탐색

 

시작 노드를 방문하고 시작 노드의 인접 노드를 우선하는 방법 (끝까지 들어가는 것이 아님)

더이상 방문할 노드가 없을 때까지 모든 노드에 BFS 적용

 

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
2. 큐 맨 앞의 노드를 꺼내고 인접 노드 중 방문하지 않은 노드를 큐에 삽입하고 방문 처리 

 

🍒 출발노드에서 목표노드까지 최단 경로 보장!

➿ 많은 기억 공간 필요

💙 최단 경로 탐색 혹은 임의 경로 탐색에 사용

 

---

 

 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int n, m, v, a, b;

bool visited[1001];
vector<int> graph[1001];

void input(){
    cin >> n >> m >> v;
    for(int i=0; i<m; i++){
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a); //중요
    }
    for(int i=1; i<=n; i++) sort(graph[i].begin(), graph[i].end()); //작은 것을 고르기로 했으므로 정렬해줌
}

void dfs(int x){
    cout << x << " ";
    visited[x] = true;
    for(int i=0; i<graph[x].size(); i++){
        int y = graph[x][i];
        if(!visited[y]) dfs(y);
    }
}

void bfs(int start){
    for(int i=0; i<1001; i++) visited[i] = false;
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while(!q.empty()){
        int x = q.front();
        cout << x << ' ';
        q.pop();
        for(int i=0; i<graph[x].size(); i++){
            int y = graph[x][i];
            if(!visited[y]){
                q.push(y);
                visited[y] = true;
            }
        }
    }
}


int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    dfs(v);
    cout << '\n';
    bfs(v);
    return 0;
}

 

 

다시 그래프 공부를 할 수 있었던 문제였다. 빨리 응용 문제를 풀어보고 싶다 ➿👾

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!