BFS

---------------------------------------------(tip1)---------------------------------------------

        0        1        2        3    . .    m 열의갯수

 

 0    (x,y)

 

 1

 

 2

 

 3

 .

 .

 n

행의갯수

---------------------------------------------(tip2)-----------------------------------------------

 전역 변수로 설정한 int 들은 0으로 초기화 된다.

 

---------------------------------------------(tip3)-----------------------------------------------

#  pair<int,int> p;

      p.first  p.second

 

# tuple<int,int,int> tup;

     get<0>(tup);

     get<1>(tup);

     get<2>(tup);

---------------------------------------------(tip4)-----------------------------------------------

 

tuple<int, char, double> t;

FloodFill

ㄴ //1.실제보드//2.방문 보드//3.상하좌우 //4.다음 방문 포인트(Q)



미로 최장거리 찾기

ㄴ //1.실제보드크기만큼의-1배열//2.실제보드를-1로 만들어서 방문보드 없애기//3.상하좌우//다음방문포인트Q

 

 

 

시작점이 두개인 토마토

ㄴ //1.실제보드//2.방문보드(0으로초기화)//3.상하좌우//4.다음방문포인트//5.날짜카운트(방문보드에 기록)  //큐에 시작점 여러개 넣고 시작

 

 

3차원의 토마토

ㄴ//1.실제보드//2.방문보드//3.상하좌우앞뒤(6칸)//4.다음방문포인트Q(pair<int,pair<int,int>>)//5.날짜카운트(방문보드기록) 

 

스타트링크

ㄴ 왜 DFS 는 안되고 BFS 만 되는가?

   ㄴ  나중에 도달한 방법이 더 빠를수 있지만, 우리는 그를 신경안써도 된다. 가장 먼저 찾은 방법만 제시하면 되기ㅒ문.

   ㄴ  bfs 알고리즘은 최단 거리를 계산해주는 알고리즘

---------------------------------------------(tip4)-----------------------------------------------

  방문에 대한기록은 ,

   q.push 하면서 동시에 이루어져야 한다.

  그렇지 않으면 무한반복 또는 메모리 초과를 맞이함

 

---------------------------------------------(tip5)-----------------------------------------------

배열의 크기가 커지면 전역변수로 사용한다.

 

​---------------------------------------------(tip5)-----------------------------------------------

1) 그래프의 모든 정점을 방문하는 것이 주요한 문제

단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용하셔도 상관없습니다.

둘 중 편한 것을 사용하시면 됩니다.

​

2) 경로의 특징을 저장해둬야 하는 문제

예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다. (BFS는 경로의 특징을 가지지 못합니다)

 

3) 최단거리 구해야 하는 문제

미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리합니다.

왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, 
너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문입니다.

 

이밖에도 

- 검색 대상 그래프가 정말 크다면 DFS를 고려
- 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS

 

출처: https://devuna.tistory.com/32 [튜나 개발일기📚]