프로그래머스 [Lv. 3] 카드 짝 맞추기 {언어 : Python}

문제 링크

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

프로그래머스

정답 코드

from collections import deque

def solution(board, r, c):
    minLength = [10000]
    # 방향 탐색
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]
    def isValid(nr, nc):
        return 0 <= nr < 4 and 0 <= nc < 4
    
    # 거리 계산
    def calCnt(ar, ac, br, bc, removes):
        if (ar, ac) == (br, bc):
            return 0
        dist = 0
        cnt = 0
        if ar == br:
            if ac > bc:
                for nc in range(ac-1, bc-1, -1):
                    if board[ar][nc] and board[ar][nc] not in removes:
                        cnt += 1
                        dist = cnt
                    else:
                        dist += 1
            else:
                for nc in range(ac+1, bc+1):
                    if board[ar][nc] and board[ar][nc] not in removes:
                        cnt += 1
                        dist = cnt
                    else:
                        dist += 1
            if cnt == 0 and (bc == 0 or bc == 3):
                dist = 1
        elif ac == bc:
            if ar > br:
                for nr in range(ar-1, br-1, -1):
                    if board[nr][ac] and board[nr][ac] not in removes:
                        cnt += 1
                        dist = cnt
                    else:
                        dist += 1
            else:
                for nr in range(ar+1, br+1):
                    if board[nr][ac] and board[nr][ac] not in removes:
                        cnt += 1
                        dist = cnt
                    else:
                        dist += 1
            if cnt == 0 and (br == 0 or br == 3):
                dist = 1
        else:
            dist1, dist2, dist3, dist4 = 0, 0, 0, 0
            cnt1, cnt2, cnt3, cnt4 = 0, 0, 0, 0
            # 왼쪽 위
            if ar > br and ac > bc:
                # 왼쪽으로 가서 위로
                for nc in range(ac-1, bc-1, -1):
                    if board[ar][nc] and board[ar][nc] not in removes:
                        cnt1 += 1
                        dist1 = cnt1
                    else:
                        dist1 += 1
                if cnt1 == 0 and bc == 0:
                    dist1 = 1
                for nr in range(ar-1, br-1, -1):
                    if board[nr][bc] and board[nr][bc] not in removes:
                        cnt2 += 1
                        dist2 = cnt2
                    else:
                        dist2 += 1
                if cnt2 == 0 and br == 0:
                    dist2 = 1
                    
                # 위로가서 왼쪽으로
                for nr in range(ar-1, br-1, -1):
                    if board[nr][ac] and board[nr][ac] not in removes:
                        cnt3 += 1
                        dist3 = cnt3
                    else:
                        dist3 += 1
                if cnt3 == 0 and br == 0:
                    dist3 = 1
                for nc in range(ac-1, bc-1, -1):
                    if board[br][nc] and board[br][nc] not in removes:
                        cnt4 += 1
                        dist4 = cnt4
                    else:
                        dist4 += 1
                if cnt4 == 0 and bc == 0:
                    dist4 = 1
                
            elif br > ar and ac > bc:
                # 왼쪽 아래
                # 왼쪽으로 가서 아래
                for nc in range(ac-1, bc-1, -1):
                    if board[ar][nc] and board[ar][nc] not in removes:
                        cnt1 += 1
                        dist1 = cnt1
                    else:
                        dist1 += 1
                if cnt1 == 0 and bc == 0:
                    dist1 = 1
                for nr in range(ar+1, br+1):
                    if board[nr][bc] and board[nr][bc] not in removes:
                        cnt2 += 1
                        dist2 = cnt2
                    else:
                        dist2 += 1
                if cnt2 == 0 and br == 3:
                    dist2 = 1
                
                # 아래로 가서 왼쪽으로
                for nr in range(ar+1, br+1):
                    if board[nr][ac] and board[nr][ac] not in removes:
                        cnt3 += 1
                        dist3 = cnt3
                    else:
                        dist3 += 1
                if cnt3 == 0 and br == 3:
                    dist3 = 1
                for nc in range(ac-1, bc-1, -1):
                    if board[br][nc] and board[br][nc] not in removes:
                        cnt4 += 1
                        dist4 = cnt4
                    else:
                        dist4 += 1
                if cnt4 == 0 and bc == 0:
                    dist4 = 1
                    
            elif ar > br and bc > ac:
                # 오른쪽 위
                # 오른쪽으로 가서 위로
                for nc in range(ac+1, bc+1):
                    if board[ar][nc] and board[ar][nc] not in removes:
                        cnt1 += 1
                        dist1 = cnt1
                    else:
                        dist1 += 1
                if cnt1 == 0 and bc == 3:
                    dist1 = 1
                for nr in range(ar-1, br-1, -1):
                    if board[nr][bc] and board[nr][bc] not in removes:
                        cnt2 += 1
                        dist2 = cnt2
                    else:
                        dist2 += 1
                if cnt2 == 0 and br == 0:
                    dist2 = 1
                    
                # 위로 가서 오른쪽으로
                for nr in range(ar-1, br-1, -1):
                    if board[nr][ac] and board[nr][ac] not in removes:
                        cnt3 += 1
                        dist3 = cnt3
                    else:
                        dist3 += 1
                if cnt3 == 0 and br == 0:
                    dist3 = 1
                for nc in range(ac+1, bc+1):
                    if board[br][nc] and board[br][nc] not in removes:
                        cnt4 += 1
                        dist4 = cnt4
                    else:
                        dist4 += 1
                if cnt4 == 0 and bc == 3:
                    dist4 = 1
                        
            else:
                # 오른쪽 아래
                # 오른쪽으로 가서 아래로
                for nc in range(ac+1, bc+1):
                    if board[ar][nc] and board[ar][nc] not in removes:
                        cnt1 += 1
                        dist1 = cnt1
                    else:
                        dist1 += 1
                if cnt1 == 0 and bc == 3:
                    dist1 = 1
                for nr in range(ar+1, br+1):
                    if board[nr][bc] and board[nr][bc] not in removes:
                        cnt2 += 1
                        dist2 = cnt2
                    else:
                        dist2 += 1
                if cnt2 == 0 and br == 3:
                    dist2 = 1
                    
                # 아래로 가서 오른쪽으로
                for nr in range(ar+1, br+1):
                    if board[nr][ac] and board[nr][ac] not in removes:
                        cnt3 += 1
                        dist3 = cnt3
                    else:
                        dist3 += 1
                if cnt3 == 0 and br == 3:
                    dist3 = 1
                for nc in range(ac+1, bc+1):
                    if board[br][nc] and board[br][nc] not in removes:
                        cnt4 += 1
                        dist4 = cnt4
                    else:
                        dist4 += 1
                if cnt4 == 0 and bc == 3:
                    dist4 = 1
                    
            dist = min(dist1+dist2, dist3+dist4)
        # print(ar, ac, br, bc, "dist", dist, removes)   
            
        return dist
    
    # 짝 위치
    dictPairs = dict()
    visitedCards = [0] * 7
    
    # 짝짓기
    for i in range(4):
        for j in range(4):
            card = board[i][j]
            if card and visitedCards[card] == 0:
                # 다른 위치 탐색
                visitedCards[card] = 1
                dq = deque([[i, j]])
                visited = [[0] * 4 for _ in range(4)]
                visited[i][j] = 1
                isFound = False
                while dq and not isFound:
                    sr, sc = dq.popleft()
                    
                    for d in range(4):
                        nr = dr[d] + sr
                        nc = dc[d] + sc
                        if isValid(nr, nc) and visited[nr][nc] == 0:
                            if board[nr][nc] == card:
                                isFound = True
                                dictPairs[card] = [i, j, nr, nc]
                                break
                            else:
                                visited[nr][nc] = 1
                                dq.append([nr, nc])
    # 지워야할 카드 개수
    lenCards = len(dictPairs)
    cards = list(dictPairs.keys())
    removeOrders = []
    visitedDfs = [0 for _ in range(7)]
    def dfs(l, visited):
        if l == lenCards:
            removeOrders.append(visited)
            return
        for card in cards:
            if card in visited:
                continue
            dfs(l+1, visited+[card])
    dfs(0, [])
    
    def calMinLength(l, order, length, sr, sc, removes):
        if minLength[0] <= length:
            return
        if l == lenCards:
            if minLength[0] > length:
                minLength[0] = length
            return
        o = order[l]
        ar, ac, br, bc = dictPairs[o]
        calMinLength(l+1, order, length + calCnt(ar, ac, br, bc, removes) + calCnt(sr, sc, ar, ac, removes), br, bc, removes+[o])
        calMinLength(l+1, order, length + calCnt(br, bc, ar, ac, removes) + calCnt(sr, sc, br, bc, removes), ar, ac, removes+[o])
                
    # 카드 지우기
    for order in removeOrders:
        calMinLength(0, order, 0, r, c, [])
    
    answer = minLength[0] + (lenCards * 2)
    return answer

풀이 방법

1. 카드의 값과 위치를 딕셔너리 형태로 저장한다.
2. 카드 제거 순서를 dfs를 통해서 만든다.
3. 카드를 제거하면서 다음과 같이 이동횟수를 계산한다.
   1. 현재 지점에서 ar, ac로 간 다음 br, bc로 가는 경우
   2. 현재 지점에서 br, bc로 간 다음 ar, ac로 가는 경우
4. 이미 제거된 카드는 ctrl + 방향키로 이동이 불가능 하다.
   1. 따라서 removes로 확인한다.
5. 카드를 모두 제거 했을 때 minLength와 비교해서 가장 적은 이동횟수로 치환한다.
6. 최소 횟수에 카드 제거 할 때 enter를 치므로 총 카드 수 * 2를 더해주면 끝!

느낀점

• 결국 도움 하나도 안 받고 풀었는데 이렇게 어려울 줄은 몰랐다...