BFS 에 대해서 배웠다. BFS 는 큐를 이용하여 탐색하는 방식이었다.
스택은 골프장 홀, 큐는 일방통행 터널느낌
큐의 작동원리를 이해한 바로는 먼저 front와 back 인덱스를 각각 -1로 잡는다.
이후 인접리스트에 저장해둔 데이터를 이용해서 front와 back인덱스를 이동시키고 back== front 가 되는 순간 반복을 종료한다.
예를 들면
인접리스트 map = {{1},{2,3},{4,5},{6,7}} 이라고 하면 back이 처음에 1이 됐을 때 map[back] 에 해당하는 배열({2,3})을 읽으며 값들은 Q에 저장하고 back 인덱스를 증가시킨다.
그러면 초기 Q ={1}에 2,3이 추가되고 back 은 0 -> 2 가 된다. 반복문이 완료되면 다시 front를 증가시켜서 2를 가리키고, map[2] 에 해당하는 값을 읽으며 Q에 추가한다.
막상 이해한 걸 말로 풀어보려니까 어려운데, 결국엔 이러한 방식으로 넓이 우선 탐색을 진행하게 된다.
int ch[10],Q[10], ft = -1, bk = -1;
vector<int> v[10];
int main(){
freopen("input.txt","rt",stdin);
int a, b;
for(int i=0; i<7; i++){
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
ch[1]=1;
Q[++bk]=1;
int x;
while(ft<bk){
x= Q[++ft];
for(int i=0; i< v[x].size(); i++){
if(ch[v[x][i]]!=1){
ch[v[x][i]]=1;
Q[++bk] = v[x][i];
}
}
}
for(int i: Q)
cout<<i<<' ';
}70. 그래프 최단거리(BFS)
int ch[21],Q[21],answer[21], ft = -1, bk = -1;
vector<int> v[21];
int main(){
freopen("input.txt","rt",stdin);
int n, m, a, b;
cin>>n>>m;
for(int i=0; i<m; i++){
cin>>a>>b;
v[a].push_back(b);
}
Q[++bk] = 1;
ch[1] = 1;
answer[1]=0;
while(ft<bk){
int x = Q[++ft];
for(int i=0; i<v[x].size();i++){
if(ch[v[x][i]]==0){
ch[v[x][i]]=1;
Q[++bk] = v[x][i];
answer[v[x][i]] = answer[x]+1;
}
}
}
for(int i = 2; i<=n; i++){
cout<<i<<" : "<<answer[i]<<endl;
}
}거리값을 설정하는 것에 대해서 고민을 했는데, 배열에서 이전 단계에 해당하는 거리에 1을 더하는 방법을 강의에서 배웠다.
