2강 - 그래프 1 (2) _ 그래프의 탐색

고작 15분짜리를 며칠만에 들었다... 연말이라 너무 쉬었어 너~~~💢

지금 큥콘 포토카드도 살지 티켓만 살지 고민중이야ㅠㅅㅠ 양갱이랑 1월 3일에 맛있는거 조지면서 큥콘 볼생각에 심장 터지는중ㅎㅎㅎㅎ

말랑인거 안숨기는 배큥💛

후 사진 고르는데 10분 걸렸다;; 매번 블로그에 공부 기록하는 것보다 사진 고르는데 진심인 편이지 후후ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

암튼 오늘은 그래프의 탐색을 공부해따!

 

-------------------------------------------------------------------------------------------------------------------------------

 

<그래프의 탐색>

- 목적 : 임의의 정점에서 시작하여 연결되어 있는 모든 정점을 한번씩 방문하는 것!

- DFS와 BFS의 차이 : 정점의 방문 순서 (어떤 정점부터 방문할지)

- DFS는 깊이 우선 탐색, BFS는 너비 우선 탐색이다

- DFS가 사람 한 명이 정점마다 방문하는 느낌이면, BFS는 사람이 복제되서 방문하는 느낌?

- DFS는 stack으로, BFS는 Queue로 구현

 

<DFS>

- Depth First Search, 깊이 우선 탐색

- 스택을 이용해서 갈 수 있는 만큼 최대한 가고 더이상 갈 수 있는 정점이 없을 때 이전 정점으로 돌아간다.

- 이 때 이전 정점을 표시하기 위해 스택을 사용한다.

- 재귀호출과 스택으로 구현하면 되고 시간복잡도는 인접행렬로 구현하면 O(V^2), 인접리스트는 O(E)이다.

인접 행렬 DFS

인접리스트 DFS

 

<BFS>

- Breadth First Search, 너비 우선 탐색

- 큐를 이용해서 지금 위치해서 갈 수 있는 정점을 모두 큐에 넣는 방식

- 큐에 넣으면 방문했다고 체크한다.

- 이는 DFS와 목적이 똑같기 때문에 시간복잡도는 동일하다.

인접행렬 BFS

인접리스트 BFS

자 이제 문제 풀어보자~

 

<1260번 / DFS와 BFS>

인접리스트만 구현해보도록 하자!! 간선리스트도 해보려고 했는데 음 edge 자료형을 처음봐서,,,ㅠㅠ

일단 인접리스트로 구현해서 dfs와 bfs의 개념이해에 중점을 두는걸루!!

 

우선 인접리스트를 이용해서 구현했다. 확실히 한 번 더 해보니까 인접리스트 이해가 좀 쉬운것 같다. dfs랑 bfs도 이해가고ㅎㅎ 제출했을때 컴파일 에러가 났는데 그건 memset함수의 헤더파일인 cstring을 선언안해서 그랬던것같다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <cstring>
//vector<pair<int, int>> edges;//간선리스트
using namespace std;
vector<int> a[2000]; //인접리스트
bool check[1001]; //방문 체크용 배열
void dfs(int x)
{
check[x] = true; //방문 체크
printf("%d ", x);
for (int i = 0; i < a[x].size(); i++)
{
int y = a[x][i];
if (check[y] == false)
{
dfs(y);
}
}
}
void bfs(int x)
{
queue<int> q;
memset(check, false, sizeof(check)); //check 배열 초기화
check[x] = true;
q.push(x);
while (!q.empty())
{
int k = q.front();
q.pop();
printf("%d ", k);
for (int i = 0; i < a[k].size(); i++)
{
int w = a[k][i];
if (check[w] == false)
{
check[w] = true;
q.push(w);
}
}
}
}
int main(void)
{
int n, m, v;
cin >> n >> m >> v;
for (int i = 0; i < m; i++)//인접리스트 생성
{
int u, v;
cin >> u >> v;
a[u].push_back(v);
a[v].push_back(u);
}
for (int i = 1; i <= n; i++) //인접리스트 정렬
{
sort(a[i].begin(), a[i].end());
}
dfs(v);
printf("\n");
bfs(v);
printf("\n");
return 0;
}

 

다음 강의는 연결 요소입니다~~