queue2 너비 우선 탐색(bfs) bfs 대해 알아보기 전에 그래프에 대한 기초가 필요하다. https://hongcode.tistory.com/32를 참고 하자. 너비 우선 탐색(bfs) BFS(Breadth First Search) 이름 뜻 그대로 임의의 정점에서 시작해서 인접한 정점을 먼저 탐색하는 방법으로, 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다. 장점 너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장 최단 경로가 존재한다면, 어느 한 경로가 무한히 깊어진다 해도 최단 경로를 반드시 찾을 수 있다. 노드 수가 적고 깊이가 얕은 해가 존재할 때 유리하다. 단점 재귀 호출을 사용하는 DFS와 달리 큐를 이용해 다음에 탐색할 노드들을.. 2022. 3. 11. 큐(Queue) Queue의 사전적 의미는 무엇을 기다리는 사람, 차량 등의 줄 혹은 줄을 서서 기다리는 것을 의미한다. 이처럼 줄을 지어 순서대로 처리되는 자료구조가 큐이다. Queue는 먼저 들어간 것이 먼저 나오는 First in First Out의 형태를 가진다. 먼저 들어간 자료가 먼저 나오는 구조 FIFO(First In FIrst Out) 구조큐는 한 쪽 끝은 프런트(front)로 정하여 삭제 연산만 수행함 다른 한 쪽 끝은 리어(rear)로 정하여 삽입 연산만 수행함 어떻게 사용하는가? #include // Queue가 포함된 헤더파일 queue q; // int형 큐 선언, 다른 자료형을 넣어도 됨 q.push(x); // 큐에 데이터 x를 입력한다. q.pop(); // 큐의 데이터를 삭제한다. q.s.. 2022. 3. 11. 이전 1 다음
