[Python] 2023 KAKAO BLIND RECRUITMENT - 표 병합

 

https://school.programmers.co.kr/learn/courses/30/lessons/150366

프로그래머스

 

이번 문제는 작년 하반기 카카오 공채 문제로 나왔던 표 병합 문제이다! union-find 문제인데 당시에 문제를 풀 때는 거의 마지막쯤에나 깨달아서 결국 효율성 점수를 받지 못했었다... 

 

union-find 알고리즘 자체가 어려운 편은 아니라 구현만 꼼꼼하게 한다면 충분히 풀 수 있는 문제다. 구현 문제인 만큼 문제를 꼼꼼히 읽고 시작하자! 

 

 

마치 엑셀을 연상시키는 것 같은 문제였는데, 엑셀과는 달리 멀리 떨어져 있는 셀끼리의 병합도 가능했다. 문제에서 주어지는 셀들이 표 형태이기 때문에 2차원 리스트 형태로 관리해야 했는데, 각각의 element들을 union-find 알고리즘을 사용하기 위해 parent 배열로 만들어줘야 했던 점이 힘들었던 것 같다. 나는 기존의 union-find 함수들을 그대로 사용하기 위해서 2차원 배열의 좌표를 선형적으로 변환해 parent 배열을 만들었다. 

 

문제에서 표의 최대 크기가 50 x 50이라는 제한을 두었기 때문에, parent 배열의 크기도 마찬가지로 51 x 51로 설정하였다. 여기에서 parent 배열의 크기가 50이 아닌 51인 이유는, 셀들의 좌표가 0이 아닌 1부터 시작하기 때문이다. parent 배열에서도 0번 인덱스는 사용하지 않는다. 

 

좌표를 인덱스로 변환하는 과정은, row 번호에는 50을 곱해주고, 이후에 col 번호를 더해주는 방식으로 구현하였다. 역으로 인덱스를 좌표로 변환할 때에는 인덱스를 50으로 나눈 몫을 row 번호로, 나머지를 col 번호로 사용했는데, 이때 col 번호가 50인 경우 나머지가 0으로 나오는 경우가 있었다. 따라서 나머지가 0인 경우 따로 예외 처리를 해주었다. 

 

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    
    parent[b] = a

def solution(commands):
    answer = []
    parent = [0] * (51 * 51)
    graph = [[0] * 51 for _ in range(51)]
    
    for i in range(len(parent)):
        parent[i] = i
    
    for command in commands:
        command = command.split()
        if command[0] == "UPDATE":
            update_command(command[1:], graph, parent)
        elif command[0] == "MERGE":
            merge_cell(parent, graph, int(command[1]), int(command[2]), int(command[3]), int(command[4]))
        elif command[0] == "UNMERGE":
            unmerge_cell(parent, graph, int(command[1]), int(command[2]))
        elif command[0] == "PRINT":
            y, x = int(command[1]), int(command[2])
            parent_idx = find_parent(parent, 50*y+x)
            if parent_idx % 50 == 0:
                value = graph[parent_idx//50-1][50]
            else:
                value = graph[parent_idx//50][parent_idx%50]
            if value == 0:
                answer.append("EMPTY")
            else:
                answer.append(value)
            
    return answer

def convert_to_idx(y, x):
    return 50 * y + x

def check_parent_value(parent, graph, x):
    x = find_parent(parent, x)
    if x % 50 == 0:
        return graph[x//50-1][50]
    return graph[x//50][x%50]

def update_parent_value(parent, graph, x, value):
    x = find_parent(parent, x)
    if x % 50 == 0:
        graph[x//50-1][50] = value
    else:
        graph[x//50][x%50] = value

def update_command(contents, graph, parent):
    if len(contents) == 3:
        idx = convert_to_idx(int(contents[0]), int(contents[1]))
        value = contents[2]
        parent_idx = find_parent(parent, idx)
        if parent_idx % 50 == 0:
            graph[parent_idx//50-1][50] = value
        else:
            graph[parent_idx//50][parent_idx%50] = value
    else:
        prev_value = contents[0]
        update_value = contents[1]
        for i in range(1, 51):
            for j in range(1, 51):
                parent_value = check_parent_value(parent, graph, 50*i+j)
                if parent_value == prev_value:
                    update_parent_value(parent, graph, 50*i+j, update_value)

def merge_cell(parent, graph, r1, c1, r2, c2):
    idx1 = 50 * r1 + c1
    idx2 = 50 * r2 + c2
    parent1 = find_parent(parent, idx1)
    parent2 = find_parent(parent, idx2)
    
    if parent1 == parent2:
        return 
    
    if parent1 % 50 == 0:
        py1, px1 = parent1//50 - 1, 50
    else:
        py1, px1 = parent1//50, parent1%50
    if parent2 % 50 == 0:
        py2, px2 = parent2//50 - 1, 50
    else:
        py2, px2 = parent2//50, parent2%50
    
    value1 = graph[py1][px1]
    value2 = graph[py2][px2]
    
    if value1 == 0:
        graph[py1][px1] = graph[py2][px2]
    
    union_parent(parent, idx1, idx2)
    
def unmerge_cell(parent, graph, r, c):
    group_num = find_parent(parent, 50*r+c)
    parent_value = check_parent_value(parent, graph, 50*r+c)
    unmerge_list = []
    for i in range(1, 51):
        for j in range(1, 51):
            idx = 50*i + j
            if find_parent(parent, idx) == group_num:
                unmerge_list.append((i, j))
    for y, x in unmerge_list:
        graph[y][x] = 0
        parent[50*y+x] = 50*y+x
    graph[r][c] = parent_value