군대에서_코딩하기_알고리즘_29

전역이 3달 채 안남았다.

하루 빨리 전역을 하고 본격적으로 공부(iOS)를 하고 싶은 마음이 절박한 상태다.😥

역시나 오랜만에 업로드이고.. 그래도 나름 공부는 꾸준히 하고 있었지만, 업로드를 할 타이밍을 놓쳐서 지금 살짝 몰아서 하려고 한다. 현시각 2022-03-03 22:27.. 23:00까지 마무리하고 얼른 올라가서 자야겠다..

우선 BFS로 넘어왔다. 지금까지는 DFS관련된 문제를 쭉 풀었었고, 이제는 BFS를 다룰 차례이다.
우선 BFS(너비 우선 탐색)란 무엇인가?

BFS란❓

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다.

• 시작점(노드)로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
• 즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.
• 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.

BFS의 특징

• DFS처럼 '재귀적'으로 동작하지 않는다.
  -> 지금까지 정리했던 DFS는 거의 대부분이 재귀함수로 구현되어있다.
• 그래프 탐색의 경우, 반드시 어떤 노드를 방문했었는지 여부를 검사해야한다.
  -> DFS의 경우도 ch[ ] 배열을 만들어서 지금껏 방문했던 노드들을 체크하곤 했었는데, 필수는 아니였다.
• BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐(Queue) 를 사용한다.
  -> 선입선출(FIFO) 원칙으로 탐색

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문을 써서 큐에 아무도 안남을때까지 돌려버리면 그냥 간단하게 끝..

오늘은 여기까지~