자료구조 및 알고리즘/백준
[백준 24444] 알고리즘 수업 - 너비 우선 탐색 1
아기사우르스
2023. 3. 31. 23:42
728x90
나의 구린 구현력
https://armembedded.tistory.com/91
이거보고 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
https://junseok.tistory.com/268?category=955870
위에 두 사람 풀이 참조했다
근데 그래프 입력 받는 거 공통 패턴 있지 않나? 그거 파악해라... 오늘 adj가 뭐하는 친구인지 까먹고 있었다.
참고로 큐는 선입선출) 뒤에서 넣고 앞에서 빼는 자료구조다
https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x06/queue_test.cpp
이거 구현해보면 안다. head에서 tail에서 각각 어떤 일을 하는지!
오늘 할 일) vector로 그래프 입력 받는 거 해보기. graph로 입력 받을 때 변수명을 adj로 하는 것보다는 graph하는게 더 직관적이다.
그리고 코드 이해하기
728x90