#BOJ 1260 DFS 와 BFS

Wonder_Why (Today I learned)·2021년 12월 17일
0

BOJ

목록 보기
6/70

🎃 DFS 와 BFS

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	157718	55222	32454	34.435%

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력 1

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력 1

1 2 4 3
1 2 3 4

예제 입력 2

5 5 3
5 4
5 2
1 2
3 4
3 1

예제 출력 2

3 1 2 5 4
3 1 4 2 5

예제 입력 3

1000 1 1000
999 1000

예제 출력 3

1000 999
1000 999

✨DFS(Depth-First-Search)

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool visited[9];
vector<int> graph[9];
// node 개수만큼 vector 생성

void dfs(int x)
{
  visited[x] = true;
  //node 'x' visited
  cout<< x << " ";
  for(int i = 0 ; i < graph[x].size();i++) // 각각 인접한 노드 사이즈만큼 탐색
  {
    int y = graph[x][i];
    if(!visited[y]) //인접 노드 방문 x라면
      dfs(y); // 방문하도록 지시
  }

}

🎇BFS(Breadth-First-Search)

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
bool visited[9];

void bfs(int start)
{
  queue<int> q;
  q.push(start); // 첫 노드
  visited[start] = true; // 방문처리
  // q 가 빌때까지 반복
  while(!q.empty())
  {
    int x= q.front();
    q.pop();
    cout << x << ' ';
    for(int i = 0 ; i <graph[x].size(); i ++)
    {
      int y = graph[x][i];
      if(!visited[y])
      {
        q.push(y);
        visited[y] = true;
      }
    }
  }
}

💎 문제 풀이

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAX = 1001;
vector<int> graph[MAX];
bool visited[MAX] = {0,};
queue<int> q;

void dfs(int x)
{
  visited[x] = true;
  //방문한 노드는 방문 처리
  cout << x << ' ';
  for(int i = 0 ; i <graph[x].size();i++)
  {
    int y = graph[x][i];
    if(!visited[y])
      dfs(y);
  }
}

void bfs(int start)
{
  q.push(start);
  visited[start] = true;
  while(!q.empty())
  {
    int x = q.front();
    q.pop();
    cout << x << ' ';
    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()
{
  int node;
  int edge;
  int starting;

  cin>>node>>edge>>starting;

  for(int i = 0 ; i<edge ; i++)
  {
    int a,b;
    cin >> a >> b;
    graph[a].push_back(b);
    graph[b].push_back(a);
   // graph[a][b] = 1;
   // graph[b][a] = 1;
  }

  for(int i = 1; i<= node ; i ++)
  {
    sort(graph[i].begin(), graph[i].end());
  }

  dfs(starting);
  cout<<'\n';

  memset(visited,false,sizeof(visited));
  bfs(starting);

  
  return 0;
}

🗝 고찰

사실 bfs, dfs 함수 구현보다, main 함수에서 input을 어떻게 받을 지를 더 고민했었다.🙄
int형 원소를 가지는 vector graph[1001]에 어떻게 입력값을 넣지?

  • 각 Node 혹은 Vertex 간의 연결된 형태를 입력해야 한다.( 1번 node와 2번 node 가 연결되어있다면 1 2 가 바로 인풋일 것)

  • 생각해보면 node/vertex 간 연결된 형태가 바로 edge 이고 edge의 개수만큼 각 node/vertex 연결 관계를 의미하는 정수 2개를 입력받는다. 그러면 edge의 갯수만큼 반복되는 루프 안에서 정수 2개를 각각 입력받고, 이를 graph 에 넣어주면 되겠다!

  • for(int i = 0 ; i < edge ; i ++) 내에서 cin >> a >> b 를 한 뒤, 차례대로 graph[a].push_back(b); graph[b].push_back(a); 를 실행하면 node/vertex 간 연결된 그래프가 만들어진다.

  • 근데, bfs / dfs 를 돌릴 때 node/vertex를 선택하는 기준은 ' 더 번호가 작은 node/vertex' 를 먼저 탐색하라고 지정되어있다.

  • 이를 어떻게 구현할까?

  • cin << a<< b 할 때, if문으로 a,b의 대소를 구분한 뒤 graph에 넣어줄까?

  • 살짝 복잡할 것 같은데, 그냥 입력은 입력대로 받은 다음에 graph에 저장된 '연결 관계를 나타내는 정수' 들을 그냥 정렬해주자.

  • for(int i = 1; i <= node ; i++) 반복문 내에서 sotr(graph[i].begin(), graph[i].end()); 를 해주자.

  • 그러면 graph[i] 에 저장된 원소들이 각각 내림차순으로 정렬된다.

  • bfs/dfs 과정에서 인덱스가 작은 노드를 먼저 탐색하도록 했으므로 문제에서 원하듯 작은 노드/정점을 먼저 탐색하게 구현이 된다!😆

  • 놓치면 안되는 게 하나 더 있는데, 각 노드를 방문 처리할 때 bool 형 1차원 배열 visited[MAX]를 사용했다. dfs 를 먼저 돌린 뒤, 각 노드의 방문 흔적이 visited 에 남아있고, 이 상태로 bfs를 돌리면 안된다!

  • 그러므로 dfs 를 돌린 뒤 visited[max]를 초기화해주어야 하는데, 이를 위해 memset을 이용했다.

  • memset 을 이용하기 위해서 cstring 을 include 하였고, memset(visited, false, sizeof(visited))로 bfs 를 돌리기 전에 방문 흔적을 초기화해주었다. (끝)

profile
전자과 머학생

0개의 댓글