문제

입력

입출력 예시

코드

#include <iostream>
#include <vector>
using namespace std;

int N, M, K;
vector<vector<int>> adj;
vector<int> visit;

pair<int, int> move(int start) {
	visit[start] = 1;
	int cnt = 1, i = 1;
	while(i <= N) {
		if(adj[start][i] && !visit[i]) {
			visit[i] = 1;
			++cnt;
			start = i;
			i = 1;
		}
		else ++i;
	}
	return {cnt, start};
}

int main() {
	cin >> N >> M >> K;
	adj = vector<vector<int>>(N + 1, vector<int>(N + 1, 0));
	visit = vector<int>(N + 1, 0);
	
	for(int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		adj[a][b] = 1;
		adj[b][a] = 1;
	}
	
	pair<int, int> ans = move(K);
	cout << ans.first << " " << ans.second;
	
	return 0;
}

이 문제는 dfs가 아니고, 그냥 그래프 순회이다!!
그리고 이전 문제들에서 재귀로 푼 경우 한두 테스트 케이스에서 런타임 에러가 났던 것을 교훈 삼아, 그냥 반복문으로 풀었다.

현재 노드(start)에서 1번 부터 N번째 노드까지 확인하며 경로가 있는지, 해당 노드를 방문했는지 확인하기 때문에 반복문이 종료되면 현재 노드에서 더이상 갈 수 있는 노드가 없는 것이다. 그래서 별도의 조건 없이 반복문이 끝나고 바로 답을 return 해주었다.