1260번 DFS와 BFS

C언어의 행렬과 C++의 vector로 구현한 DFS와 BFS 문제이다.  

나중에 C언어의 연결리스트로 구현한 코드도 업로드 하겠다.

특히, 이러한 Skill의 경우 각종 응용 문제에서 많이 활용되니 꼭 기억해두자. 

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

C언어 행렬

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
int N = 0, M = 0, V = 0;
 
int Graph[1001][1001] = { 0, };
 
int visit[1001] = { 0, };
 
int queue[1001] = { 0, };
 
void DFS(int start)
{
    printf("%d ", start);
 
    visit[start] = 1;
 
    for (int i = 1; i <= N; i++)
    {
        if (Graph[start][i] == 1 && visit[i] == 0)
        {
            DFS(i);
        }
    }
}
 
void BFS(int start)
{
    int front = 0, rear = 0, pop = 0;
 
    printf("%d ", start);
    
    visit[start] = 1;
 
    queue[rear++] = start;
 
    while (front < rear)
    {
        pop = queue[front++];
 
        for (int i = 1; i <= N; i++)
        {
            if (Graph[pop][i] == 1 && visit[i] == 0)
            {
                printf("%d ", i);
 
                queue[rear++] = i;
                visit[i] = 1;
            }
        }
    }
}
 
int main(void)
{
    int from = 0, to = 0;
 
    memset(visit, 0, sizeof(visit));
    memset(Graph, 0, sizeof(Graph));
 
    scanf("%d %d %d", &N, &M, &V);
 
    for (int i = 0; i < M; i++)
    {
        scanf("%d %d", &from, &to);
 
        Graph[from][to] = 1;
        Graph[to][from] = 1;
    }
 
    DFS(V);
    printf("\n");
 
    memset(visit, 0, sizeof(visit));
 
    BFS(V);
    printf("\n");
 
    return 0;
}

C++ vector

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>
 
using namespace std;
 
int N = 0; // 정점의 개수
 
int M = 0; // 간선의 개수
 
int V = 0; // 탐색을 시작할 정점의 번호
 
vector<vector<int> > adj; // 인접 리스트
 
queue<int> q;
 
int visit[1001] = { 0, };
 
void Add_adj(int s, int e) // 간성 생성
{
    adj[s].push_back(e);
    adj[e].push_back(s);
}
 
void Sort_adj() // 정렬
{
    for (int i = 1; i <= N; i++)
    {
        sort(adj[i].begin(), adj[i].end());
    }
}
 
void DFS(int start) // 깊이 우선 탐색
{
    printf("%d ", start); // 출력
 
    visit[start] = 1;
 
    for (int next : adj[start])
    {
        if(visit[next] == 0) DFS(next);
    }
 
    /*for (int i = 0; i< adj[start].size(); i++)
    {
        int next = adj[start][i];
        if (visit[next] == 0) DFS(next);
    }*/
}
 
void BFS(int start) // 너비 우선 탐색
{
    q.push(start);
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        for (int i = 0; i < qSize; i++)
        {
            int here = q.front();
 
            q.pop();
 
            if (visit[here] == 1) continue; // 1이면 무시(방문했다는 뜻)
 
            visit[here] = 1; // 방문 
 
            printf("%d ", here);
             
            for (int i = 0; i < adj[here].size(); i++)
            {
                q.push(adj[here][i]);
            }
        }
    }
     
    /*
    while (N>0)
    {
      for (int next : adj[start])
      {
          if (visit[next] == 0) // 방문 하지 않았다면,
          {
              printf("%d ", next);
 
              visit[next] = 1; // 방문처리 해주고
 
              q.push(next); // 큐에 담는다.
          }
      }
 
      if (!q.empty())
      {
          start = q.front();
          q.pop();
      }
 
      --N;
    }
    */
}
 
int main(void)
{
    int vs = 0, ve = 0;
 
    scanf("%d %d %d", &N, &M, &V);
 
    adj.resize(N + 1);
 
    for (int i = 1; i <= M; i++)
    {
        scanf("%d %d", &vs, &ve);
 
        Add_adj(vs, ve);
    }
     
    Sort_adj();
 
    DFS(V);
 
    memset(visit, 0, sizeof(visit));
 
    printf("\n");
 
    BFS(V);
 
    printf("\n");
 
    return 0;
}