[Python] 소셜 네트워킹 어플리케이션 (백준 7511 파이썬)

문제

어렸을때부터 컴퓨터 프로그래밍에 엄청난 소질을 보인 상근이는 항상 소셜 네트워킹 웹사이트를 만들고 싶어 했다. 상근이는 페이스북을 벤치마킹하기 위해 지난 3년간 열심히 사용을 했고, 이제 페이스북의 단점을 보완한 새 소셜 네트워킹 웹 2.0 어플리케이션을 만들려고 한다.

사람들은 소셜 네트워킹 어플리케이션에 가입을 한 다음, 현실에서 아는 사람을 친구로 추가하기 시작한다. 이러한 친구 관계 정보를 이용해 친구 관계 그래프를 그릴 수 있다.

소셜 네트워킹 어플리케이션에서 가장 중요한 기능은 한 사람이 다른 사람의 페이지를 방문했을 때, 친구 관계 그래프에서 두 사람 사이의 경로를 보여주는 기능이다. 경로가 없는 경우에는 보여주지 않는다.

상근이의 서비스는 매우 유명해졌고, 위의 기능은 사람들이 점점 많아질수록 경로를 구하는 시간이 매우 느려지게 되었다. 그 이유는 두 사람 사이의 경로가 없는 경우에 경로를 찾기 위해 너무 오랜시간 그래프를 탐색하기 때문이었다. 따라서, 상근이는 두 사람 사이의 경로가 존재하는지 안 하는지를 미리 구해보려고 한다.

유저의 수와 각 유저의 친구 관계가 입력으로 주어진다. 이때, 주어지는 두 사람이 친구 관계 그래프상에서 경로가 존재하는지 안 하는지를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 유저의 수 1 ≤ n ≤ 106이 주어진다. 둘째 줄에는 친구 관계의 수 1 ≤ k ≤ 105가 주어진다. 다음 k개 줄에는 두 정수 0 ≤ a, b < n이 주어진다. 두 수는 친구 관계를 나타내며, 유저 a와 b가 친구라는 소리이다. 다음 줄에는 미리 구할 쌍의 수 1 ≤ m ≤ 105가 주어진다. 다음 m개 줄에는 구해야하는 쌍을 나타내는 u, v가 주어진다.

출력

각 테스트 케이스마다 "Scenario i:"를 출력한다. i는 테스트 케이스 번호이며, 1부터 시작한다. 그 다음, 각각의 쌍마다 두 사람을 연결하는 경로가 있으면 1, 없으면 0을 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

예제 입력 1 복사

2
3
1
0 1
2
0 1
1 2
5
3
0 1
1 2
3 4
2
0 2
1 3

예제 출력 1 복사

Scenario 1:
1
0

Scenario 2:
1
0

 

 

 

문제 풀이

처음 풀이를 시도했을 때, 단순 그래프 입력 후 간선 찾기 문제라고 생각했으나 구현하면서 유니온 파인드로 해결하는 문제임을 알았습니다.

 

전체 케이스 수를 입력받은 뒤, 각 케이스를 진행합니다.

N = int(input())
F = int(input())

parent = list(range(N)) # 부모(루트)가 누구인지 기록하는 배열
rank = [0] * N

# 친구 관계 입력
for _ in range(F):
    a, b = map(int, input().split())
    union(parent, rank, a, b)

 

그래프의 정보(친구 관계)를 입력받고 경로를 연결하는 union 함수를 실행합니다.

 

union 함수, find 함수

def union(parent, rank, x, y):
    root_x = find(parent, x)
    root_y = find(parent, y)

    # 부모가 다르면 합쳐야함, 합칠때 더 큰 그래프쪽으로 합치기(rank)
    if root_x != root_y:
        if rank[root_x] > rank[root_y]:
            parent[root_y] = root_x
        elif rank[root_x] < rank[root_y]:
            parent[root_x] = root_y
        else:
            parent[root_y] = root_x
            rank[root_x] += 1
            
 # x집합의 부모찾기
def find(parent, x):
    # x가 부모가 아니면 재귀 돌려서 반복
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

 

이후 두 사람이 친구관계인지 파악합니다.

친구관계 라는 것은 경로가 연결되었다는 뜻이므로 find 함수를 통해 부모가 같은지 파악합니다.

 

m = int(input())
result = []

for _ in range(m):
    u,v = map(int, input().split())

    # 경로 존재 => 같은 부모(같은 집합)
    if find(parent, u) == find(parent, v):
        result.append(1)
    else:
        result.append(0)

print(f"Scenario {t+1}:")
for r in result:
    print(r)
print()

 

 

 

 

코드

# 7511 소셜 네트워킹 어플리케이션

# 유니온파인드
# union => 합치기
# find => 부모 찾기
# parent => 자기 자신을 부모로 하는 노드
# rank => 초기 높이

# x집합의 부모찾기
def find(parent, x):
    # x가 부모가 아니면 재귀 돌려서 반복
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, rank, x, y):
    root_x = find(parent, x)
    root_y = find(parent, y)

    # 부모가 다르면 합쳐야함, 합칠때 더 큰 그래프쪽으로 합치기(rank)
    if root_x != root_y:
        if rank[root_x] > rank[root_y]:
            parent[root_y] = root_x
        elif rank[root_x] < rank[root_y]:
            parent[root_x] = root_y
        else:
            parent[root_y] = root_x
            rank[root_x] += 1

T = int(input())

for t in range(T):
    N = int(input())
    F = int(input())

    parent = list(range(N)) # 부모(루트)가 누구인지 기록하는 배열
    rank = [0] * N

    # 친구 관계 입력
    for _ in range(F):
        a, b = map(int, input().split())
        union(parent, rank, a, b)


    m = int(input())
    result = []

    for _ in range(m):
        u,v = map(int, input().split())

        # 경로 존재 => 같은 부모(같은 집합)
        if find(parent, u) == find(parent, v):
            result.append(1)
        else:
            result.append(0)

    print(f"Scenario {t+1}:")
    for r in result:
        print(r)
    print()