작은 노드

문제

풀이

문제를 정확히 이해하는데 시간이 소요된 문제였다.
무작정 연결된 노드를 모두 구하는 것이 아니라, 주어진 조건으로 갈 수 있는 노드만 구해야 한다.

첫번째 예시로 문제를 해석해보면 이렇다.
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번 노드부터 시작한다.

• 1번 노드와 직접 연결된 노드 중 방문 가능하고 가장 작은 노드는 2번 노드이다.
• 2번 노드와 직접 연결된 노드 중 방문 가능하고 가장 작은 노드는 3번 노드이다.
• 3번 노드와 직접 연결된 노드 중 방문 가능하고 가장 작은 노드는 4번 노드이다.
• 4번 노드와 직접 연결된 노드 중 방문 가능하고 가장 작은 노드는 6번 노드이다.
• 6번 노드와 직접 연결된 노드 중 방문 가능한 노드는 없다.

따라서 총 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;
}

여담

구름톤 챌린지에 참여하기 잘했다고 생각하는게, 문제가 완전 베이직하다. 그래서 여태까지 공부했었던 알고리즘을 복기하는데에도 좋고 내가 부족한 파트도 충분히 파악할 수 있었다.

물론 기업 코테에서는 이것보다 훨씬 어려운 문제들이 나오지만, 그 문제의 근간이 되는 문제를 풀다보니 재미있고 자신감도 얻게 된다.

가끔씩 난감한 문제들도 보이지만 할만하다. 재밌다~.~