Assignment 2 - Merging tables

날짜:
Assignment 2 - Merging tables

과제 2의 마지막문제는 데이터베이스에 있는 테이블들을 합치는 것이다. 합친 후 데이터베이스에 있는 테이블의 최대 크기, 즉 최대 행을 구하는 문제이다.


과제의 설명을 보면 다음과 같은 순서를 통해 문제해결을 지시한다.
선결조건은 n개의 테이블이 데이터베이스에 있으며 테이블들의 number(index)는 1부터 n까지 이다.

1. destinationi이라는 table number(index)에 symbolic link가 연결되어 있다면 이를 다시금 연결된 테이블을 destinationi로 변경한다. (마치 부모노드를 찾는 것처럼)
2. sourcei라는 table number또한 마찬가지로 symbolic link를 통해 변경한다.
3. destinationi, sourcei값을 비교하고 만약 두개의 테이블이 같지 않다면 sourcei의 행들을 (행의 갯수를) destinationi의 행에 붙여 넣고 sourcei의 테이블은 0으로 초기화 한다.
4. n개의 테이블 중 가장 큰 테이블의 행의 갯수를 출력한다.

Input format
n m (테이블의 총 갯수, merge명령 수행 횟수)
r1 r2 ... ri (i번째 테이블의 행 갯수)
k (merge명령을 수행할 2개의 테이블, 총 m개)

Output format
s (최대크기의 테이블에 해당하는 행의 갯수)


 예시인 Sample 1을 보면 n은 5, m이 5이다. 그리고 각각 테이블의 행의 갯수는 1이며 이후에 merge 명령을 수행할 테이블들이 나열되고 있다. 먼저 3, 5번째 테이블을 병합하므로 3번째가 destination, 5번째가 source가 된다. 5번째 테이블의 행의 갯수인 1을 3번째 테이블의 행의 갯수에 더해주면 2가 되고 5번째 테이블의 행의 갯수는 0이 되며 symbolic link를 3으로 연결한다. 다음 2, 4번째도 마찬가지로 진행하며 이제 1, 4번째 테이블을 보면 destination이 1번째, source가 4번째 테이블이 되는데 4번째 테이블은 symbolic link로 2번째 테이블로 연결되어 있기 때문에 결국 1, 2 테이블의 병합을 수행하는 것으로 된다. 따라서 2번째 테이블의 행의 갯수인 2를 1번째로 넣어 1번 테이블의 행의 갯수는 3이 되며 2번 테이블은 0으로 초기화 되고 symbolic link는 1번 테이블로 연결된다. 이 때 최대 행의 갯수는 3이 될 것이다.


아무래도 예시를 보면서 이해하는 것보다는 코드로 바로 넘어갈 때가 더 도움이 되는 듯 하다.

# python3
import sys

n, m = map(int, sys.stdin.readline().split())
lines = list(map(int, sys.stdin.readline().split()))
rank = [1] * n
parent = list(range(0, n))
ans = max(lines)


def getParent(table):
    # find parent and compress path    
    return parent[table]


def merge(destination, source):
    realDestination, realSource = getParent(destination), getParent(source)

    if realDestination == realSource:
        return False
    # merge two components    
    # use union by rank heuristic     
    # update ans with the new maximum table size        
    return True

for i in range(m):
    destination, source = map(int, sys.stdin.readline().split())
    merge(destination - 1, source - 1)
    print(ans)

 기초 코드로 넘어가보자. 위와 같이 n, m을 변수로 받고 lines를 통해 테이블들의 행의 갯수를 입력받으며 rank를 통해 우선순위를 설정하고 parent를 통해 symbolic link가 어디로 연결되는지 알 수 있다. ans는 위에서 본 것처럼 최대 행의 갯수를 반환받는 변수이다.
 getParent를 통해 symbolic link를 반환받을 뿐 아니라 경로압축까지 진행해야 하며 merge에서는 destination, source에 해당하는 테이블들의 병합을 진행한다. 이때 rank heuristic에 의거하여 병합을 진행해야하며 ans를 업데이트 하여야 한다.

# python3
import sys

n, m = map(int, sys.stdin.readline().split())
lines = list(map(int, sys.stdin.readline().split()))
rank = [1] * n
parent = list(range(0, n))
ans = max(lines)


def getParent(table):
    # find parent and compress path    if parent[table] == table:
        return table
    else:
        parent[table] = getParent(parent[table])
        return parent[table]


def merge(destination, source):
    realDestination, realSource = getParent(destination), getParent(source)

    if realDestination == realSource:
        return False
    # merge two components    # use union by rank heuristic     # update ans with the new maximum table size
    parent[realSource] = realDestination
    lines[realDestination] += lines[realSource]
    lines[realSource] = 0
"""    
    elif rank[realDestination] > rank[realSource]:    
    parent[realSource] = realDestination    
    lines[realDestination] += lines[realSource]     
    lines[realSource] = 0

    elif rank[realDestination] < rank[realSource]:    
    parent[realDestination] = realSource     
    lines[realSource] += lines[realDestination]    
    lines[realDestination] = 0

    else:    
    parent[realSource] = realDestination    
    rank[realDestination] += 1    
    lines[realDestination] += lines[realSource]    
    lines[realSource] = 0
    return True
"""
for i in range(m):
    destination, source = map(int, sys.stdin.readline().split())
    merge(destination - 1, source - 1)
    ans = max(lines)
    print(ans)

 아직 과제를 통과하진 못했지만 더는 지체할 시간과 여력이 없어 중간 코드를 게시한다. getParent에서는 위에 명시한 동작을 수행하도록 작성하였고 merge 부분이 약간 애매하여 두가지로 작성하였다.
 우선 과제에 명시된대로만 한다면 주석부분을 제외하고도 처리가 가능하다. 하지만 rank heuristic을 활용하여 연산속도를 내기를 원하는 것으로 보이기에 주석처리와 같은 부분을 추가했었다. 하지만 두 방법 모두 제한시간을 초과하는 모습을 보여 더이상 진행이 불가했다. 추후 시간을 내서 다시금 업데이트를 해봐야겠다.

나중에 하기에 자꾸 아른거려서 Googling을 해보니 아래 링크와 같이 누군가 친히 똑같은 과제에 대해 같은 문제(time limit)을 언급했다. 덕분에 참고하여 잘 해결 할 수 있었다!

# python3
import sys

n, m = map(int, sys.stdin.readline().split())
lines = list(map(int, sys.stdin.readline().split()))
rank = [1] * n
parent = list(range(0, n))
ans = max(lines)


def getParent(table):
    # find parent and compress path    if parent[table] == table:
        return table
    else:
        parent[table] = getParent(parent[table])
        return parent[table]


def merge(destination, source):
    global ans
    realDestination, realSource = getParent(destination), getParent(source)

    if realDestination == realSource:
        return False
    # merge two components    # use union by rank heuristic     # update ans with the new maximum table size
    if rank[realSource] > rank[realDestination]:
        realSource, realDestination = realDestination, realSource
    parent[realSource] = realDestination
    lines[realDestination] += lines[realSource]
    rank[realDestination] += lines[realSource]
    lines[realSource] = 0    ans = max(ans, lines[realDestination])


for i in range(m):
    destination, source = map(int, sys.stdin.readline().split())
    merge(destination - 1, source - 1)
    print(ans)

원인은 for문 내에서 lines에 대해 지속적으로 max값을 찾는 프로세스때문에 시간이 오래걸렸던 것이었다. 따라서 for문 돌때마다 max값을 lines 전체에서 찾는 것이 아닌 merge에서 병합을 추진할 때 새로 병합한 테이블의 행이 최대값일 가능성이 크니 이전 최대값과 비교하면 된다.

https://stackoverflow.com/questions/39242472/disjoint-sets-path-compression-running-time-error

댓글

댓글 쓰기