[Python] 백준 '친구 네트워크' 4195번 | 해시 Union-Find, 집합, 그래프 자료구조 문제

다른 문제 모음집

문제

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.

어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

출력

친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

---

반응형

풀이

test_case = int(input())


# find 재귀 함수 : x의 찐부모를 찾을 떄 까지 find
def find(x):
    if x == parent[x]:
        return x
    else:
        parent[x] = find(parent[x])
        return parent[x]


# x의 부모를 찾고, y의 부모를 찾음. 서로 부모가 다르면 x의 부모를 일치시킴.
def union(x, y):
    x_ = find(x)
    y_ = find(y)
    
    # x, y 의 부모가 서로 다른 경우, x 부모로 일치. num 딕셔너리에 자식 수 셈.
    if x_ != y_:
        parent[y_] = x_
        num[x_] += num[y_]


for _ in range(test_case):
    friends = int(input())

    parent = dict()
    num = dict()
    for _ in range(friends):
        x, y = input().split()

        if x not in parent:
            parent[x] = x
            num[x] = 1
        if y not in parent:
            parent[y] = y
            num[y] = 1

        union(x, y)
        print(num[find(x)])

• 처음 문제를 읽을 때, 뭔 개소리를 하는지 모르겠었다... Union-Find의 개념이 없으면 이해를 못할 것 같은 느낌... 그리고 헷갈리고 애매한게 많다... 갑자기 "두 사람"을 말하길래 누굴 말하는 건지 생각하다가 먼 산으로 갈 뻔했다, 테스트 케이스를 2개 줘서 "두 사람의 친구 네트워크"라고 한 것 같다.... 그래프 개수가 여러개면 어떤 그래프의 친구 수가 출력 되어야 하는 것도 그러하다...
• Union-Find 문제 (부모(parent)와 자식(child) 테이블 존재) / 친구 이름을 입력 받을 때, (x, y)를 받는다고 하면, x <- y 의 방향으로 부모와 자식 관계를 형성 (부모 <- 자식). 예를 들면, 처음 Fred Barney라는 입력은 "Fred <- Barney", 두 번째로 Barney Betty 입력은 "Fred <- Betty"가 된다. "Fred <- Barney <- Betty " 결국엔 "Fred <- Betty"가 된다. 즉, Fred가 최종 부모인 역할임. (그림으로 이해하면 더 쉽다. 친구를 노드로 생각해서 그린 뒤에 화살표를 붙임)  그럼 이 상황에서 출력을 생각하면, Fred라는 부모는 Barney와 Betty까지 총 3명으로 네트워크를 구성했다. 문제에서 입력으로 준 두 번째 케이스는, 두 번째 줄에서, 두 개의 친구 네트워크로 구성된 후, 마지막에 Barney와 Betty가 친구가 되면서 모든 친구들이 Fred를 부모로 갖게 된다. "Fred <- Barney <- Betty <- Wilma" = 총 4명으로 구성
• Union-Find의 개념을 살짝 말하자면,  dictionary 자료형의 key와 value 값을, key는 모든 구성원(=노드), value는 그 구성원의 부모를 나타낸다. (dict['구성원'] = 부모) >> 노드의 부모가 달라질 수 있기 떄문에 이러한 구조
• parent 딕셔너리는 {자기 이름:부모} 의 구조로 있음. (부모 갱신 됨)
• num  딕셔너리는 {자기 이름:숫자}의 구조이지만, 결국 부모가 되는 이름에 숫자가 쌓임
• 풀이한 코드로 최종 parent 를 출력해보면 Wilma의 부모가 Betty라고 나오는데, 코드 상, 마지막에 wilma의 찐부모를 찾는 find함수가 실행되지 않음.(=그럴 필요가 없음) 답을 위한 코드로는 맞지만, 개념적으로는 틀림.  num로 구성원 수를 출력했기 때문에 문제 없음. 다음 입력이 또 주어지면 알아서 정리됨. >> 더 좋은 코드를 생각 못하겠음.

출처

Contest > Waterloo's local Programming Contests > 27 September, 2008 C번