[프로그래머스] 카드 짝 맞추기

 

아이디어 도출 방법

 

1. 먼저 방향성, 최단 거리등의 키워드를 통해서 BFS 탐색이 떠올랐다.

• 하지만 이동 타입이 두 개라는 점이 생각을 어지럽게 했다. 언제는 cntrl 키를 눌러서 이동해야 하고, 언제는 한 칸만 이동하면 될까 -> 결국 4*4의 맵임으로 완전 탐색으로 진행하기로 했다. 

2. 같은 카드가 두 개 있는데 무엇부터 시작해야 할까? (A:어파치 카드1, A1:어파치 카드2)

• 처음에는 그리디 하게 X- > A와 X -> A1 비용 중 싼 이동 가격으로 완전 탐색을 진행했다. 하지만 틀렸다. 그리디는 최적이 아니다. 
• 따라서 모든 순서에서 시작해야 한다. X -> A -> A1로 가는 것과 X -> A1-> A로 가는 것은 종료 위치가 달라지기에 결과 값에 영향을 미칠 수 있다.

 

 아이디어는 어렵지 않지만 구현은 어려웠다. 

1. BFS 구현

• 초기에는 아래와 같이 작성했다.
  • 하나의 for문에 방향키로 움직일 경우와 , 해당 cntrl + 방향키를 눌렀을 경우를 동시에 계산하도록 했더니 제대로 된 답이 나오지 않았다. 
  • 여기서 더욱 심각한 문제는 테스트를 어떻게 진행해야 할지 감이 잡히지 않는다는 점이었다.

def bfs(board, sx, sy, rx , ry):
    queue = deque()
	#cost 배열 초기화
    visited =[[987654321] * 4 for _ in range(4)]
    
    #시작 위치 
    queue.append([sx, sy, 0])
    visited[sx][sy] = 0

    while queue:
        ox, oy, cost = queue.pop()

        if ox == rx and oy == ry:
            return cost

        for dx, dy in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            mx = ox + dx
            my = oy + dy
			
            #한번만 움직일 경우 
            if not check_out_range(mx, my):
                if cost + 1 < visited[mx][my]:
                    visited[mx][my] = cost + 1
                    queue.append([mx, my, cost + 1])
            else:
                continue
			#cnrl키로 움직일 경우
            while not check_out_range(mx + dx, my + dy) and board[mx + dx][my + dy] == 0:
                mx = mx + dx
                my = my + dy

            if cost + 1 < visited[mx][my]:
                visited[mx][my] = cost + 1
                queue.append([mx, my, cost + 1])

 

2. 완전 탐색 구현 

• 해당 코드에는 두 가지 문제점이 존재했다.
  • 완전 탐색이긴 하나 제대로 된 답을 반환하지 않는다.  왜냐하면 이중 포문 안을 보면 dfs를 호출하면서 answer의 최소 값을 받는데 움직임을 계산하는 코드를 보면 answer에 계산된 값을 더해주고 있다. 즉 현재 움직임을 계산한 값을 잃는다. 
  • 템플릿 미스
    
    • 나는 최상단에 재귀 탐색의 종료 조건을 적고 다음 블록에는 계산 코드를 작성했었다. 하지만 해당 습관이 깨지면서 오류 코드를 작성했다. 

def dfs(board, sx, sy, rx, ry):
    temp_board = deepcopy(board)

    answer = 0
    
    answer += bfs(temp_board, sx, sy, rx, ry) #도착 한 곳
    point = temp_board[rx][ry]
    temp_board[rx][ry] = 0

    rrx, rry = get_card_point(temp_board, point)
    answer += bfs(temp_board, rx, ry, rrx, rry)
    temp_board[rrx][rry] = 0

    answer += 2

    for i in range(4):
        for j in range(4):
            if temp_board[i][j] != 0:
                answer = min(answer, dfs(temp_board, rrx, rry, i, j))

    return answer

def solution(board, r, c):
    answer = 987654321

    for i in range(4):
        for j in range(4):
            if board[i][j] != 0:
                answer = min(answer, dfs(board, r, c, i, j))

    return answer

개선된 버전

def dfs(board, sx, sy):
    is_end = TRUE

    for i in range(4):
        for j in range(4):
            if board[i][j] != 0:
                is_end = False
                break

        if not is_end:
            break

    if is_end:
        return 0
    
    answer = 987654321

    for rx in range(4):
        for ry in range(4):
            if board[rx][ry] != 0:

                doll_num = board[rx][ry]
                board[rx][ry] = 0
                fx, fy = get_card_point(board, doll_num)

                move_cnt = bfs(board, sx, sy, rx, ry)
                move_cnt += bfs(board, rx, ry, fx, fy)

                board[fx][fy] = 0

                move_cnt += 2
                answer = min(answer, dfs(board, fx, fy) + move_cnt)

                board[rx][ry] = doll_num
                board[fx][fy] = doll_num

    return answer

 

후기

구현 문제는 시간을 너무 오래 잡아먹는다. 적당한 테스트 방법을 모르겠다. 다시 한번 TDD 책을 읽고 어떤 방식으로 진행하면 좋을지 연구해보자