처음 생각해낸 방법이지만, 오류가 있는 풀이이다.
1. dfs를 2번까지만 반복한다는 생각으로 시작했다.
2. 1번(주인공)에 대해서 첫번째 친구에 대해서 탐색을 하고, 그친구의 친구를 탐색한다.
3. 두번째 친구를 탐색하고, 그 친구의 친구까지 탐색을 한다.
4. 탐색된 노드는 중복이 되지않게 방문 true처리를 바로바로 해준다.
void solv(){
for(auto w : graph[1]) {
if (!visited[w]) {
visited[w]=true;
ans++;
for(auto v : graph[w]){
if (!visited[v]) {
visited[v]=true;
ans++;
}
}
}
}
}
당연하게도, dfs로 저렇게 풀게되면 친구의 친구가 탐색되지 않는경우가 생긴다.
친구가 탐색될 순서가 오기전에 먼저 탐색되면 그 뒤에 친구는 탐색되지 않는다 말이 복잡한데 반례를 보면 간단하다
4
4
1 2
1 3
2 3
3 4
이렇게 되면 4번노드는 탐색되지않고 오답인 2(2, 3)이 출력된다.
void solv(){
visited[1]=true;
for(auto w : graph[1]){
friends.push_back(w);
}
for(auto w : friends){
visited[w]=true;
for(auto v : graph[w]){
if (!visited[v]) {
visited[v]=true;
}
}
}
for (int i=2; i<=n; i++) {
if (visited[i]) {
ans++;
}
}
}