[백준][C++]1260번 DFS와 BFS

문제

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

1260번: DFS와 BFS

 

 

풀이

DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 알고리즘

DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 알고리즘

 

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

void DFS(int n);
void BFS(int n);
static vector<vector<int>> graph;
static vector<bool> visited;

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

  int N, M, V;
  cin >> N >> M >> V;

  graph.resize(N + 1);
  visited.resize(N + 1);
  // 인접 리스트 graph에 그래프 데이터 저장
  for(int i = 0; i < M; i++)
  {
    int a, b;
    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());
  }
  
  fill(visited.begin(), visited.end(), false);	// 방문 배열 초기화
  DFS(V);
  cout << "\n";
  fill(visited.begin(), visited.end(), false);
  BFS(V);
  
  return 0;
}

// DFS 구현
void DFS(int n)
{
  visited[n] = true;	// visited 배열에 현재 노드 방문 기록
  cout << n << " ";	// 현재 노드 출력
  
  // 현재 노드의 연결 노드 중 방문하지 않은 노드에 대해 DFS 실행
  for(int node : graph[n])
  {
    if(visited[node] == false)
    {
      DFS(node);
    }
  }
}

// BFS 구현
void BFS(int n)
{
  queue<int> myqueue;
  myqueue.push(n);	// 큐 자료구조에 시작 노드 넣기
  visited[n] = true;	// visited 배열에 현재 노드 방문 기록
  
  while(!myqueue.empty())
  {
    int now = myqueue.front();	// 큐에서 노드 데이터를 가져오기
    myqueue.pop();
    cout << now << " ";	// 가져온 노드 출력
    
    // 현재 노드의 연결 노드 중 방문하지 않은 노드에 대해 큐에 데이터를 삽입하고 visited 배열에 방문 기록
    for(int node : graph[now])
    {
      if(visited[node] == false)
      {
        myqueue.push(node);
        visited[node] = true;
      }
    }
  }
}