[백준/C++] 1269번_DFS와 BFS

문제는 다음과 같습니다.

전형적인 dfs와 bfs를 구하는 문제입니다.
이 문제의 조건을 살펴보면,
"단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고 ..." 라고 되어있는데
이 부분때문에 이 문제에서는 인접리스트가 아닌 인접행렬을 이용하였습니다.

그래서 2차원 배열인 v[1001][1001]을 이용하였습니다.

dfs는 스택호출을 이용한 재귀를,
bfs는 큐 자료구조를 이용하였고
각각을 함수로 만들어 실행하였습니다.

전체 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

int n, m, start;
int v[1001][1001]={0, };
int ch1[1001]={0, };
int ch2[1001]={0, };
queue<int> q;

void DFS(int k){
  cout<<k<<" ";

  for(int i=1; i<=n; i++){
    if(v[k][i]==1 && ch1[i]==0){
      ch1[i]=1;
      DFS(i);
    }
  }
}

void BFS(int k){
  while(!q.empty()){
    cout<<q.front()<<" ";
    int tmp = q.front();
    q.pop();

    for(int i=1; i<=n; i++){
      if(v[tmp][i]==1 && ch2[i]==0){
        ch2[i]=1;
        q.push(i);
      }
    } // for문 끝

  } // while문 끝
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>m>>start;

    for(int i=0; i<m; i++){
      int a, b; cin>>a>>b;
      v[a][b]=1; v[b][a]=1;
    }

    ch1[start]=1;
    DFS(start);
    cout<<endl;

    ch2[start]=1;
    q.push(start);
    BFS(start);

    return 0;
}

2/16 수요일 복습)

#include <bits/stdc++.h>
 using namespace std;

 int v[1001][1001];
 int ch[1001]={0, };
 int n, m, s, state=1;

 void DFS(int k){
   cout<<k<<" ";

   for(int i=1; i<=n; i++){
     if(v[k][i]==1 && ch[i]==0){
       ch[i]=1;
       DFS(i);
     }
   }
 }

 void BFS(int k){
   queue<int> q;
   ch[k]=1; q.push(k);

   while(!q.empty()){
     int tmp = q.front(); q.pop();
     cout<<tmp<<" ";

     for(int i=1; i<=n; i++){
       if(v[tmp][i]==1 && ch[i]==0){
         ch[i]=1;
         q.push(i);
       }
     } // for문 끝

   } // while문 끝

 }

 int main() {
     ios_base::sync_with_stdio(false);
     cin.tie(nullptr);

     cin>>n>>m>>s;
     for(int i=0; i<m; i++){
       int t1, t2; cin>>t1>>t2;
       v[t1][t2]=1; v[t2][t1]=1;
     }

     // DFS수행
     ch[s]=1;
     DFS(s);
     cout<<"\n";
     memset(ch, 0, sizeof(ch)); // ch배열 초기화

     // BFS수행
     BFS(s);

     return 0;
 }