전역이 3달 채 안남았다.
하루 빨리 전역을 하고 본격적으로 공부(iOS)를 하고 싶은 마음이 절박한 상태다.😥
역시나 오랜만에 업로드이고.. 그래도 나름 공부는 꾸준히 하고 있었지만, 업로드를 할 타이밍을 놓쳐서 지금 살짝 몰아서 하려고 한다. 현시각 2022-03-03 22:27.. 23:00까지 마무리하고 얼른 올라가서 자야겠다..
우선 BFS로 넘어왔다. 지금까지는 DFS관련된 문제를 쭉 풀었었고, 이제는 BFS를 다룰 차례이다.
우선 BFS(너비 우선 탐색)란 무엇인가?
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다.
[참고] https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html
처음에는 익숙하지 않아서 어색했는데, 사용하다보니 Queue라는 자료구조는 정말.. 신세계에 가깝다. vector보다 편한듯...?
우선 BFS 첫번째 기본적인 문제다.
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
int ch[30], dis[30];
//ch은 왔던 곳을 체크, dis는 1번에서부터의 거리를 담아줄 배열
int main(){
int N, M, a, b, x;
vector<int> map[30];//방향 그래프의 정보를 담아줄 vector 배열
queue<int> Q;
cin>>N>>M;
for(int i=0; i<M; i++){
cin>>a>>b;
map[a].push_back(b); //이렇게 인접 그래프로 할 경우 매우 편함..
//전글인가? 전전글에 이유 적어놨음. 경로의 가능여부?를 다시 한번
//체크해주지 않아도 되기 때문에.
}
Q.push(1);
ch[1] = 1;
while(!Q.empty()){//Q가 빌때까지
x = Q.front();
Q.pop();
for(int i=0; i<map[x].size(); i++){
if(ch[map[x][i]]==0){//아직 가지 않았으면 if문에 걸림
ch[map[x][i]]=1;
Q.push(map[x][i]);//탐색해야하는 정점이 쌓임
dis[map[x][i]] = dis[x] + 1; //거리 누직
}
}
}
for(int i=2; i<=N; i++){
cout<< i <<" : "<< dis[i]<<endl;
}
}
기본적에 기본적인 문제였고 다음 문제는 BFS를 응용한 문제이다.
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
int ch[30]={0,};
//왔다간 여부를 확인하기 위한 배열 + 현재의 깊이..?를 표시
int main(){
int S, E, a;
//S가 출발지점, E가 도착지점
int temp[3] = {1, -1, 5};
//temp배열을 굳이 만들어준 이유는..보다 간결한 코드를 위해..?
queue<int> Q;
cin>>S>>E;
Q.push(S);//S부터 시작이니 당연히 Q에 S부터 넣는다.
ch[S] = 1;//마찬가지로 S부터 시작이니, S는 거쳤다는것을 표기.
//한번 거쳐던 지점은 의미없음.
while(!Q.empty()){
a = Q.front();
Q.pop();
for(int i=0; i<3; i++){
if(a+temp[i]==E){//현 위치가 E(목표 지점)이면 프로그램 종료
cout<<ch[a];
exit(0);
}
if(ch[a+temp[i]]==0){//아직 가보지 못한 곳이면
ch[a+temp[i]]=ch[a] + 1;//이부분 중요!!!
Q.push(a+temp[i]);
}
}
}
}
위 코드중에서 개인적으로
ch[a + temp[i]] = ch[a] + 1;
이 부분이 가장 중요하다고 생각하는데, 위 문제에서 ch배열은 단순히 왔다 갔다는 여부만을 표시하기 위한 배열이 아닌, 현 노드 위치의 깊이..?를 표시하기 위한 배열이다. 그렇기 때문에, 새로운 정점을 발견하면, 새로운 정점까지 가는데 소요되는 거리를 계속해서 누적하는 것이다.
마지막 문제다.
예전에 한번 풀었던 문젠데, queue를 이용해서 푸는 문제다.
아마 내 기억상으로는 배열..?인가 포인턴가를 이용해서 풀었던걸로 기억하는데 큐를 이용하니까 너무 깔끔하게 코드가 짜인다.
코드는 다음과 같다.
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int N, K, x;
queue<int> Q;
cin>>N>>K;
for(int i=1; i<=N; i++){
Q.push(i);
}
while(!Q.empty()){
for(int i=1; i<=K; i++){
if(i!=K){
x = Q.front();
Q.pop();
Q.push(x);
}
else{
x = Q.front();
Q.pop();
}
}
}
cout<<x;
}
어차피 K의 배수에 걸리는 왕자..?만 제외하니까, 그 이외의 사람들은 다시 뒷번호로 넣어버리는 것이다.. 이렇게 하지 않으면 다시 배열을 만들던가 해야하는데, 그냥 while문을 써서 큐에 아무도 안남을때까지 돌려버리면 그냥 간단하게 끝..
오늘은 여기까지~