프로그래머스 [Lv. 3] 표 병합 {언어 : Python}

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/150366?language=python3

프로그래머스

정답 코드

from collections import deque

def solution(commands):
    adjL = [[[] for _ in range(51)] for _ in range(51)]
    valueBoard = [["" for _ in range(51)] for _ in range(51)]
    def strToint(r, c):
        return int(r), int(c)
    
    def update1(sr, sc, value):
        visited = [[0] * 51 for _ in range(51)]
        dq = deque([[sr, sc]])
        visited[sr][sc] = 1
        valueBoard[sr][sc] = value
        while dq:
            r, c = dq.popleft()
            if not adjL[r][c]:
                continue
            for nr, nc in adjL[r][c]:
                if visited[nr][nc]:
                    continue
                visited[nr][nc] = 1
                valueBoard[nr][nc] = value
                dq.append([nr, nc])
        return visited
    
    def update2(value1, value2):
        visited = [[0] * 51 for _ in range(51)]
        for r in range(51):
            for c in range(51):
                if visited[r][c] or valueBoard[r][c] != value1:
                    continue
                visited = update1(r, c, value2)
    
    def unmerge(sr, sc):
        visited = [[0] * 51 for _ in range(51)]
        dq = deque([[sr, sc]])
        visited[sr][sc] = 1
        while dq:
            r, c = dq.popleft()
            for nr, nc in adjL[r][c]:
                if visited[nr][nc]:
                    continue
                visited[nr][nc] = 1
                valueBoard[nr][nc] = ""
                dq.append([nr, nc])
            adjL[r][c] = []
        adjL[sr][sc] = []
    
    answer = []
    for command in commands:
        arr = command.split(" ")
        how = arr[0]
        if how == "UPDATE":
            if len(arr) == 4:
                r, c, value = int(arr[1]), int(arr[2]), arr[3]
                update1(r, c, value)
            else:
                how, value1, value2 = arr
                update2(value1, value2)
        elif how == "MERGE":
            r1, c1, r2, c2 = int(arr[1]), int(arr[2]), int(arr[3]), int(arr[4])
            if r1 == r2 and c1 == c2:
                continue
            adjL[r1][c1].append([r2, c2])
            adjL[r2][c2].append([r1, c1])
            value = ""
            value1 = valueBoard[r1][c1]
            value2 = valueBoard[r2][c2]
            if value1:
                value = value1
            else:
                value = value2
            update1(r1, c1, value)
        elif how == "UNMERGE":
            r, c = int(arr[1]), int(arr[2])
            unmerge(r, c)
        else:
            # PRINT
            r, c = int(arr[1]), int(arr[2])
            value = valueBoard[r][c]
            if not value:
                value = "EMPTY"
            answer.append(value)
    return answer

풀이 방법

• 변수 설정
  • adjL : r, c가 주어졌을 때 r, c와 연결된 위치 [p, q]를 가지고 있는 [] 빈 배열을 가진 3차원 배열
    • 예를 들어 1, 1과 2, 3이 merge 된다면 => adjL[1][1] = [[2, 3]] 형태를 가진다.
  • valueBoard : 값을 저장하는 2차원 배열
• update1함수
  • r, c, value가 주어지면 r, c와 연결된 위치를 adjL[r][c]에서 찾는다.
  • 다음 위치 nr, nc로 이동하면서 value 값으로 바꾼다.
  • 방문 배열을 return 한다.
• update2함수
  • update1을 사용한다.
  • value1을 value2로 바꾼다는 말은 혹시나 병합된 value1의 위치값들을 value2로 바꾼다는 말이므로 update1을 재사용한다.
  • 어차피 한 번 방문한 곳은 다시 방문할 필요 없으니 update1의 방문 배열을 가지고 와서 visited에 치환한다.
• merge
  • 양방향으로 위치를 저장해준다.
  • 이 과정에서도 update를 해야한다.
    • 왜냐하면 이미 병합이 이루어진 위치 nr, nc와 병합이 이루어진다면 넓어진 범위까지 value값으로 update해야 하기 때문이다.
    • 예를 들어
      • MERGE 1 1 3 3 인 경우 
      • A 무리 : [1, 1], [1, 2], [2, 2]
      • B 무리 : [3, 3], [3, 4], [4, 4]
      • A 무리와 B무리가 합쳐진다면 [1, 1], [1, 2], [2, 2], [3, 3], [3, 4], [4, 4]가 되고 모두 value값으로 바꿔야 한다.
• unmerge
  • 하나씩 방문하면서 값을 없애고 adjL[nr][nc]값 또한 초기화 한다. (빈 배열로 만들어서 연결된 위치 값이 없게 만든다.)
  • 여기서 adjL[sr][sc] 시작 지점 또한 초기화 해야 한다.
• print
  • 빈 값이면 EMPTY
  • 있으면 answer에 그대로 넣으면 끝!

느낀점

• 문제를 꼼꼼하게 읽어서 그런지 오래 걸렸지만 답을 보지 않고 풀 수 있었다