글 읽기 - 2533 사회망 서비스(sns) 질문입니다.

bjs1409 9년 전 0

sns 너무 어렵네요 ㅠㅠ

저는 이 문제를 조건을 보면서 최소인 early adaptor 조건은

leaf즉, 트리의 끝점들은 early adaptor가 아니고 leaf의 부모가 early adaptor이면

된다고 생각을 하고 있습니다. 그럼 최초의 트리에서 early adaptor를

결정한 합니다.(물론 early adaptor를 결정할때는 해당 정점의 연결된 간선의 수가 1일때 결정을 하였습니다.)

정해진 early adaptor를 정점으로 그 하위 트리를 기존의 트리에서 삭제 한다고

생각을 하고 부모와 연결되는 간선을 없앴습니다.

그리고 리메이크된 기존트리에서 다시 leaf들을 찾고 위과정을 반복하였습니다.

이런식으로 ealry adaptor를 결정하면 문제가 되는 경우가 뭔지 알고싶습니다.

#include<cstdio>
#include<vector>
#include<set>
using namespace std;

vector<int> degree, visited;
vector<set<int> > adj;
int N;

int main(){
	freopen("input.txt", "r", stdin);
	scanf("%d", &N);
	degree = visited = vector<int>(N);
	adj = vector<set<int> >(N);

	for (int i = 0; i < N - 1; i++){
		int u, v; scanf("%d%d", &u, &v);
		degree[u - 1]++;
		degree[v - 1]++;
		adj[u - 1].insert(v - 1);
		adj[v - 1].insert(u - 1);
	}
	int count = 0;
	int ans = 0;
	vector<int> leaf;

	for (int i = 0; i < N; i++){
		if (degree[i] == 1){
			leaf.push_back(i);
		}
	}
	
	while (true){
		int l = leaf.size();
		vector<int> tmp;
		for (int i = 0; i < l; i++){
			int v = leaf[i];
			int u = *adj[v].begin();
			adj[v].erase(u);
			adj[u].erase(v);
			degree[v]--;
			degree[u]--;
			count += 2;
			if (!visited[u]){
				ans++;
				visited[u] = true;
			}
			if (count == 2 * (N - 1)){
				printf("%d", ans);
				return 0;
			}

			if (degree[u] == 1){
				int uu = *adj[u].begin();
				adj[u].erase(uu);
				adj[uu].erase(u);
				degree[u]--;
				degree[uu]--;
				count += 2;
				if (count == 2 * (N - 1)){
					printf("%d", ans);
					return 0;
				}
				tmp.push_back(uu);
			}
		}
		leaf = tmp;
	}
}

pichulia 9년 전 0

예제를 하나 줘볼께요..

정답은 5개인데 위의 코드로는 7이 나옵니다.

1 2

1 3

1 4

1 5

1 6

2 7

3 8

4 9

5 10

8 11

9 12

9 13

9 14

9 15

9 16

정확히 뭐라 말하긴 힘든데... 아마

얼리어답터라고 정할 수 있는 사람이 2명 이상일 때

둘 중에 누구를 먼저 제거하냐에 따라서

불필요한 얼리어답터가 추가되는 경우가 있는걸로 생각됩니다.

pichulia 9년 전 1

와 TLE 날 줄 알았는데 맞아버렸네요...

님 소스코드에서 문제가 되는 경우는 크게 2개가 있는데

하나는 tmp.push_back(uu);

uu노드가 leaf가 아닐 수 있는데도 leaf vector에다가 넣은 것이고요

이건 단순 실수나까 if(degree[uu] == 1) 을 추가해서 고칠 수 있습니다.

또다른 하나는 leaf 노드가 얼리어답터인 경우였습니다.

이 경우, 즉 소스코드상에서는 v가 얼리어답터라서 visited[v] == true인 경우겠죠?

이런 경우에도 현재 코드는 묻지도 따지지도 않고 u를 visitied[u] = ture 로 만들어버립니다.

v가 얼리어답터인 리프인 경우 경우 v의 부모인 u가 얼리어답터일 필요가 없지요

이게 나오지 않는 예제는

1 2

1 3

3 4

1 5

5 6

6 7

7 8

8 9

9 10

10 11

11 12

12 13

13 14

14 15

이와 같으며(정답은 7인데 이 소스코드로는 8이 나옴)

이 경우 visited[v] == true인 경우에 대해서 예외처리를 해주는 것으로 해결했습니다.

2.6초가 걸려서 답이 나온, 수정된 소스코드를 첨부합니다.

    while (true){
        int l = leaf.size();
        vector<int> tmp;
        for (int i = 0; i < l; i++){
            int v = leaf[i];
            if(degree[v]!=1)continue;
            int u = *adj[v].begin();
            adj[v].erase(u);
            adj[u].erase(v);
            degree[v]--;
            degree[u]--;
            count += 2;
            if (!visited[v] && !visited[u]){
                ans++;
                visited[u] = true;
            }
            if (count == 2 * (N - 1)){
                printf("%d", ans);
                return 0;
            }
            if (degree[u] == 1){
                if(visited[u])
                {
                    int uu = *adj[u].begin();
                    adj[u].erase(uu);
                    adj[uu].erase(u);
                    degree[u]--;
                    degree[uu]--;
                    count += 2;
                    if (count == 2 * (N - 1)){
                        printf("%d", ans);
                        return 0;
                    }
                    if(degree[uu] == 1)
                    tmp.push_back(uu);
                }
                else
                    tmp.push_back(u);
            }
        }
        leaf = tmp;
    }

bjs1409 9년 전 1

pichulia님 정말 감사합니다! ㅎㅎ 드디어 해결했네요 ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2533 사회망 서비스(sns) 질문입니다.

bjs1409 9년 전 0

pichulia 9년 전 0

pichulia 9년 전 1

bjs1409 9년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말