[c++] BFS example from 바킹독

728x90

BFS (Breadth First Search)

: 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘

예를 들어, 위와 같은 배열에서 파란색 지역을 탐색하는 알고리즘이다.

시작은 좌측 상단(0,0)에서부터 상,하,좌,우의 인접한 배열의 값들을 방문하여 파란색 좌표를 search한다.

이때, 그림에서 오른쪽과 같이 queue의 자료구조를 이용해, 현재 탐색하는 배열의 (행,열)의 번호를 저장한다.

새로운 파란색 점이 나올시 쌓이며(push), 이전에 탐색한 파란색 점의 정보는 제거한다(pop).

queue가 비워질때까지 계속한다.

queue는 #include<utility>에 있는 pair라는 쌍 자료형을 받을 수 있는 객체를 사용해서 queue에 쌓아준다. 관련 내용은 아래 링크에서 자세히 확인 할 수 있습니다.

[c++] <STL> pair 사용법

pair는 두 종류의 데이터 타입을 하나로 묶어, 한번에 전달 할 수 있음 서로 연관된 2개의 데이터를 한 쌍으로 묶어서 처리할 때 편리하다. 아래와 같이 여러 데이터 타입을 묶어서 사용할 수 있음

forward-gradually.tistory.com

구체적은 코드는 다음과 같습니다.

아래는 유용한 BFS에 대한 설명 자료입니다. 이를 참고하였습니다.

728x90

관련글