[백준 24444] 알고리즘 수업 - 너비 우선 탐색 1

나의 구린 구현력

https://armembedded.tistory.com/91

[백준 24479] 알고리즘 수업 - 깊이 우선 탐색 1

이거보고 E는 adj라고 눈치채고 풀었지만 -- 그러니까 인접리스트 adj는 E

구현은 요것밖에 안 했다.

 

수도 코드가 다음과 같은데

한 구현은

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define fio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

using namespace std;

int n,m,s,a,b,idx=1;
vector<int> adj[100005]; //인접리스트 E
// 인접리스트를 큐 형식으로?? - 아니

int answer[100005];
bool visited[100005];



void bfs(int cur){ // 바킹독님 코드랑 원리는 비슷
   for (int x: ){ // 여기
    visited[x]=false; // 각 코드에서 왜 false하고 true하는지 알아봐요
   }
   visited[cur]=true;

   queue<int> Q;// bfs 한 번 할 때 큐 하나 생성하고...
   Q.push(cur); // # 큐 맨 뒤에 시작 정점
    while(!Q.empty()){
        Q.pop();
        for(int x: ){ // 대문자 E는 adj
        visited[x]=true;
        Q.push(x);

        }


    }




}

int main(){
    fio;
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++){
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i = 1; i <= n; i++){
        sort(adj[i].begin(), adj[i].end());
    }

    bfs(s);
    for (int i = 1; i <= n; ++i) {
        cout << answer[i] << '\n';
    }
    return 0;
}

 

다른 사람 풀이를 참고하자... 구현력을 늘리자 임마;;

 

https://kiveiru.tistory.com/m/24

[C++] 백준 24444번 알고리즘 수업 - 너비 우선 탐색 1

https://junseok.tistory.com/268?category=955870 

백준 24444 - 알고리즘 수업 - 너비 우선 탐색 1 (C++)

위에 두 사람 풀이 참조했다

근데 그래프 입력 받는 거 공통 패턴 있지 않나? 그거 파악해라... 오늘 adj가 뭐하는 친구인지 까먹고 있었다.

 

 

 

참고로 큐는 선입선출) 뒤에서 넣고 앞에서 빼는 자료구조다

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x06/queue_test.cpp

GitHub - encrypted-def/basic-algo-lecture: 바킹독의 실전 알고리즘 강의 자료

이거 구현해보면 안다. head에서 tail에서 각각 어떤 일을 하는지!

 

오늘 할 일) vector로 그래프 입력 받는 거 해보기. graph로 입력 받을 때 변수명을 adj로 하는 것보다는 graph하는게 더 직관적이다.

그리고 코드 이해하기