결혼식

---

잘못된 풀이

처음 생각해낸 방법이지만, 오류가 있는 풀이이다.
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)이 출력된다.

올바른 풀이

1. 친구들을 탐색하면서 벡터에 추가한다.
2. 벡터에 있는 요소와 그들의 친구를 방문을 체크하면서 탐색한다.
3. 탐색된 노드의 개수만큼 ans를 올린다(1번노드일때는 올리면 안된다)

---

코드

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++;
        }
    }
}

---

참고

https://velog.io/@venniek/백준C-5567-결혼식 반례참고