문제를 정확히 이해하는데 시간이 소요된 문제였다.
무작정 연결된 노드를 모두 구하는 것이 아니라, 주어진 조건으로 갈 수 있는 노드만 구해야 한다.
첫번째 예시로 문제를 해석해보면 이렇다.
n=6, m=5, k=1이고 주어진 노드를 그림으로 그리면 다음과 같다.
여기서 각 노드별로 이어진 노드를 표로 표현하면 다음과 같다.
1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|
2 | 1 | 1 | 3 | 3 | 4 |
3 | 3 | 2 | 6 | ||
4 | |||||
5 |
k가 1이므로 1번 노드부터 시작한다.
따라서 총 5번 이동하고 마지막에 방문하게 되는 노드는 6번 노드이다.
풀어서 써보면 어떻게 풀어야할지 감이 잡히는데, 눈대중으로 풀어보니 그게 잘 안 됐다.
그래서 조건을 조금씩 추가하다보니 완성했다. 이번에도 bfs로 풀었고 내가 필요하다고 느낀 몇가지 조건... 뭐 break나 sort같은 부가 조건에 신경쓰며 풀었다.
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int n,m,k,f,s;
vector<int> v[2001];
bool visit[2001] = {false};
void bfs(int k){
int s=0, e=k;
queue<int> q;
q.push(k);
while (!q.empty()){
int tmp=q.front();
q.pop();
if (visit[tmp]==false){
s++;
visit[tmp]=true;
e=tmp;
}
for(int i=0;i<v[tmp].size();i++){
if (visit[v[tmp][i]]==true)
continue;
q.push(v[tmp][i]);
break;
}
}
cout<<s<<" "<<e<<endl;
}
int main() {
cin>>n>>m>>k;
for(int i=0;i<m;i++){
cin>>f>>s;
v[f].push_back(s);
v[s].push_back(f);
}
for (int i=1;i<=n;i++){
sort(v[i].begin(),v[i].end());
}
bfs(k);
return 0;
}
구름톤 챌린지에 참여하기 잘했다고 생각하는게, 문제가 완전 베이직하다. 그래서 여태까지 공부했었던 알고리즘을 복기하는데에도 좋고 내가 부족한 파트도 충분히 파악할 수 있었다.
물론 기업 코테에서는 이것보다 훨씬 어려운 문제들이 나오지만, 그 문제의 근간이 되는 문제를 풀다보니 재미있고 자신감도 얻게 된다.
가끔씩 난감한 문제들도 보이지만 할만하다. 재밌다~.~