[백준/c++] 1260번: DFS와 BFS

문제 링크 - https://www.acmicpc.net/problem/1260

🌱 문제

🌱 풀이

입력받기

• 간선 정보를 입력받아서 인접리스트에 저장한다.
• vector 배열을 통해 각 정점에 연결된 정점을 push_back 한다.
• 한 점에서 방문할 수 있는 정점이 여러개인 경우, 정점 번호가 작은것을 먼저 방문해야 하므로 전체 벡터를 돌면서 오름차순 정렬한다.

🌻 DFS - 깊이 우선탐색

• DFS는 stack 방식을 이용하지만, 재귀함수 또한 구조가 stack과 같기 때문에 재귀함수로 구현한다.

1. 정점을 방문했으므로 check한다.
2. 현재 정점의 벡터 사이즈만큼 for문을 돌면서 인접한 정점을 확인한다
3. 아직 방문하지 않은 정점인지 확인하고 dfs(해당정점)을 호출한다.

🌻 BFS - 넓이 우선탐색

• BFS는 queue를 이용한다 + while문
• 시작 정점을 queue에 삽입하고 방문 처리를 한다.
• queue가 빌 때까지 while문을 수행한다.
• queue의 front를 다른 변수에 보관후 pop하고, for문을 통해 해당 정점에 인접한 정점들을 queue에 넣는다.
• queue자체에 정점들이 한번씩만 들어가야되므로, push 할때 방문 처리를 해야한다
  ( queue에 넣을 때 방문처리 안하고, 출력 전에 방문처리 했다가 헤맴)
• 모든 정점을 방문했으면 queue에 넣을게 없으므로 pop되면서 queue가 비면서 끝난다.

memset

• dfs, bfs에서 같은 check배열을 사용하므로 dfs가 끝나면 배열을 0으로 초기화 해준 후 bfs를 실행한다.
• 헤더파일 <'cstring'> 선언
• 사용 방식 : memset(배열이름, 초기화 하고자하는 값, 배열 사이즈)
  • ex) memset(arr,0,sizeof(arr));
• *주의 : 초기화 값은 0 또는 char 타입만 가능하다.
  • memset 함수는 1 바이트 단위로 값을 초기화하기 때문에.
  • 4바이트로 표현된 int(ex. 1, 2, 3 등)형은 초기화 불가능 하다.

🌱 코드

//1260번. DFS와 BFS
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

int n,m,start;
vector<int> v[1001];
queue<int> q;
bool check[1001];

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

}

void bfs(int x){
    q.push(x);
    check[x]=true;
    while(!q.empty()){
        int y=q.front();
        cout<<y<<" ";
        q.pop();
        for(int i=0; i<v[y].size(); i++){
            int a=v[y][i];
            if(check[a]==false)
                q.push(a);
                check[a]=true;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n>>m>>start;
    for(int i=0; i<m; i++){
        int from, to;
        cin>>from>>to;
        v[from].push_back(to);
        v[to].push_back(from);
    }
    
    for(int i=1; i<=n; i++){
        sort(v[i].begin(), v[i].end());
    }

    dfs(start);

    cout<<"\n";
    memset(check,false,sizeof(check));

    bfs(start);


}

참고 사이트
https://blockdmask.tistory.com/441