컴공 일기223
게시글 주소: https://dev.orbi.kr/00061333779
bfs(breadth first searching) 알고리즘을 학습하고 있습니다. 어.. 직접 구현하는 것이 아무래도 도움이 많이 되겠지요.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> v[1001];
bool visit[1001];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin >> T;
for (int t = 0; t < T; t++)
{
int nation, edge;
cin >> nation >> edge;
for (int i = 1; i <= nation; i++)
{
v[i].clear();
visit[i] = false;
}
for (int i = 0; i < edge; i++)
{
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
int cnt = 0;
queue<int> q;
q.push(1);
visit[1] = true;
while (!q.empty())
{
int idx = q.front();
q.pop();
for (int i = 0; i < v[idx].size(); i++)
{
int next = v[idx][i];
if (!visit[next])
{
visit[next] = true;
cnt++;
q.push(next);
}
}
}
cout << cnt << '\n';
}
}
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
추억이다
bfs 넘모 어려워...
백준 많이 풀어보세요 !! 알고리즘은 이론보다는 실제로 PS하면서 증명도 해보고, 활용도 하면서 배우는부분이 많습니다!
앗 사실 이게 백준 문제 풀어본건데! 그림도 그려보고, 문제도 많이 풀어봐야 겠어요! 감사합니다 :)
갠적으로 제가 올림피아드 준비하면서 많이했는데, 코드 앞에서 고민하는 시간보다는 손으로 직접 순서도라던지 예제 입력 만들어가면서 생각해보고 알고리즘 설계 능력 키우는데는 더 좋아요!! 코드치는 시간보다는 고민하는 시간에 더 투자하심이 !!
다익스트라랑 같이 배우면 조은
다익스트라 알고리즘... 벨만-포드 알고리즘...
음수 가중치를 가진 간선에 대한 처리들... 그 부분도 재미있지요 :-)
적록색약 풀어보시죠사실 지금 시점에서 정리할 때는 코드보다도 왜 쓰이는가, 어떤 부분에서 효율적인가, BFS나 DFS나 아니면 알고리즘들이 내부적으로 자료구조를 뭘 쓰는가. 그리고 왜 그 자료구조를 쓰는가. 이런 걸 정리해야 할 거 같아요 ㅎㅎ 구현은 나중에 하다보면 손이 기억하니까요
조언 감사드립니다 :) 말씀주신 대로, 알고리즘보다는 자료구조가 훨씬 중요한 것 같아요! 마음 급해지지 않고 천천히 기본부터!
말씀 새기겠습니다 ㅎ_ㅎ
컴공일기님은 노력충 재능충 뭐라고 생각하시나여?!
컴공이 노력으로 커버 가능한 영역일까요?
할 수 있는 게 노력뿐이라면 노력은 내 삶의 전부겠지요 ㅎㅎ