[Programmers] P150366 표 병합

[Programmers] P150366 표 병합

Question

Language: Python

해당 문제는 주어진 명령어에 따라서 표를 편집하는 과정을 구현하면 되는 문제이다.

해당 문제의 핵심은 표의 병합을 어떻게 처리할 것이냐에 달려있다. 병합을 처리하기 위해 multiple-disjoint set을 활용한다. 병합을 수행하고 난 이후에는 현재 좌표에 실제 좌표가 매칭이 안되기 때문에 find_parent_compressed을 활용하여 현재 좌표에 매칭된 실제 좌표를 활용하여 명령어를 수행한다.

MERGE, UNMERGE

핵심적인 연산인 MERGE, UNMERGE은 아래와 같이 union_parents의 기본 구조와 유사하게 동작한다.

def merge(row1,col1,row2,col2):
    exact_row1,exact_col1=find_exact_coordinates(row1,col1)
    exact_row2,exact_col2=find_exact_coordinates(row2,col2)
    
    #이미 같은 셀인 경우
    if [exact_row1,exact_col1]==[exact_row2,exact_col2]:
        return

    #부모 노드 결합 진행
    parents[exact_row2][exact_col2]=[exact_row1,exact_col1]
    
    #병합된 셀에 값 저장
    array[exact_row1][exact_col1]=array[exact_row1][exact_col1] if array[exact_row1][exact_col1] else array[exact_row2][exact_col2]

    #갱신된 부모 노드값 전파
    for row in range(51):
        for col in range(51):
            find_exact_coordinates(row,col)
    
    
def unmerge(target_row,target_col):
    #병합을 해제할 좌표의 실제 좌표 구하기
    parent_row,parent_col=find_exact_coordinates(target_row,target_col)
    #병합된 셀의 값
    previous_value=array[parent_row][parent_col]

    #각각의 좌표에 대해서 병합된 셀에 포함된 좌표에 대해서 실제 좌표값을 초기화하는 작업을 진행한다.
    for row in range(1,51):
        for col in range(1,51):
            if find_exact_coordinates(row,col) == [parent_row,parent_col]:
                parents[row][col]=[row,col]
                array[row][col]=""
    
    #최종적으로 기존 병합된 셀의 값을 명령어를 수행한 좌표에 값 저장
    array[target_row][target_col]=previous_value

Solution

def find_exact_coordinates(row,col):
    if [row,col] != parents[row][col]:
        parents[row][col]=find_exact_coordinates(parents[row][col][0],parents[row][col][1])
    return parents[row][col]

def update_by_coordinate(row,col,value):
    exact_row,exact_col=find_exact_coordinates(row,col)
    array[exact_row][exact_col]=value
    
    
def update_by_value(value1,value2):
    for row in range(1,51):
        for col in range(1,51):
            exact_row,exact_col=find_exact_coordinates(row,col)
            if array[exact_row][exact_col]==value1:
                array[exact_row][exact_col]=value2
    

def merge(row1,col1,row2,col2):
    exact_row1,exact_col1=find_exact_coordinates(row1,col1)
    exact_row2,exact_col2=find_exact_coordinates(row2,col2)
    
    #이미 같은 셀인 경우
    if [exact_row1,exact_col1]==[exact_row2,exact_col2]:
        return

    #row1,col1이 값이 있는 경우
    parents[exact_row2][exact_col2]=[exact_row1,exact_col1]
    #병합된 셀에 값 저장
    array[exact_row1][exact_col1]=array[exact_row1][exact_col1] if array[exact_row1][exact_col1] else array[exact_row2][exact_col2]
    
    #갱신된 부모 노드값 전파
    for row in range(51):
        for col in range(51):
            find_exact_coordinates(row,col)
    
    
def unmerge(target_row,target_col):
    parent_row,parent_col=find_exact_coordinates(target_row,target_col)
    previous_value=array[parent_row][parent_col]
    for row in range(1,51):
        for col in range(1,51):
            if find_exact_coordinates(row,col) == [parent_row,parent_col]:
                parents[row][col]=[row,col]
                array[row][col]=""
    
    array[target_row][target_col]=previous_value

def print_value(row,col):
    exact_row,exact_col=find_exact_coordinates(row,col)
    cell_value=array[exact_row][exact_col] if array[exact_row][exact_col] != "" else "EMPTY"
    answer.append(cell_value)
    

def print_board(array):
    for row in array[1:5]:
        print(row[1:5])
        
def solution(commands):
    global array,parents,answer
    answer = []
    array=[[""] *51 for _ in range(51)]
    parents=[[[row,col] for col in range(51)] for row in range(51)]

    
    for command in commands:
        segment=command.split(" ")
        operation=segment[0]
        
        if operation=="UPDATE":
            #"UPDATE r c value"
            if len(segment) == 4:
                row,col,value=segment[1:]
                update_by_coordinate(int(row),int(col),value)
            #"UPDATE value1 value2"   
            else:
                value1,value2=segment[1:]
                update_by_value(value1,value2)
            
                            
        #"MERGE r1 c1 r2 c2"
        elif operation=="MERGE":
            row1,col1,row2,col2=map(int,segment[1:])
            merge(row1,col1,row2,col2)

                
        #"UNMERGE r c"
        elif operation=="UNMERGE":
            row,col=map(int,segment[1:])
            unmerge(row,col) 

        #"PRINT r c"
        else:
            row,col=map(int,segment[1:])
            print_value(row,col)
          
    return answer