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

이 문제는 힌트를 얻고 나서 푼 문제

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

프로그래머스

 

문제는 4x4 격자에서 같은 그림의 카드를 뒤집는 최소 횟수를 구하는 문제이다.

문제를 보자마자 4x4 격자의 크기, 최소 횟수 구하는 문제로 완전탐색을 해야하고 bfs와 dfs를 모두 사용해야 되겠다는 것은 알았다.

bfs는 최단거리 dfs는 어떤 카드를 먼저 뒤집느냐에 따라서 결과가 달라지기에 필요하다. 

 

하지만 일반적인 bfs와 다르게  ctrl + 방향키가 있는 점이 살짝 구현하기 귀찮았다. 

이부분부터 살짝 꼬여서 한번에 못 풀었던 같다.

바로 costMap을 설정하고 이것을 갱신하면서 BFS를 돌리면 되는 것을 엉뚱한데 꽂혀가지고 결국 힌트를 봤다.

 

다시한번 최단 거리를 구하는 문제는 costMap을 작성하면 풀릴수 있다는 것을 머리속에 기억해 놔야 겠다.

 

문제 풀이를 요약하면 다음과 같다.

1. 현재 시점에서 뒤집을 수 있는 카드들을 dfs를 이용하여 모두 시도해 본다.

2. 현재 위치에서 뒤집을려고 하는 카드까지 드는 최소거리와 첫번째 카드에서 두번째 같은 그림의 카드까지의 최소거리를 bfs로 구한다.

3. 뒤집을 카드가 없을때까지 1번, 2번을 반복한다.

 

from copy import deepcopy
from collections import deque

INF = 10 ** 2

answer = INF


def solution(board, r, c):
    global answer
    hashMap = {}
    enterCount = 0
    for y in range(4):
        for x in range(4):
            key = board[y][x]
            if key != 0:
                enterCount += 1
                if key in hashMap:
                    hashMap[key].append((y, x))
                else:
                    hashMap[key] = [(y, x)]


    for value in hashMap.values():
        for ny, nx in value:
            count = bfs(board,r,c,ny,nx)
            dfs(board,ny,nx,count,hashMap)


    return answer + enterCount


def bfs(board, r, c, ty, tx):
    dx = [1, 0, 0, -1]
    dy = [0, 1, -1, 0]
    costMap = [[INF] * 4 for _ in range(4)]
    costMap[r][c] = 0
    queue = deque([(r, c)])



    while queue:
        y, x = queue.popleft()

        if y == ty and x == tx:
            return costMap[y][x]

        # 한칸씩 이동할때
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx and nx < 4 and 0 <= ny and ny < 4:
                if costMap[ny][nx] > costMap[y][x] + 1:
                    costMap[ny][nx] = costMap[y][x] + 1
                    queue.append((ny, nx))
        # ctrl 경우
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 4방향에 대해서 0이 아닐때까지 계속 돌림
            while 0 <= ny + dy[i] < 4 and 0 <= nx + dx[i] < 4 and board[ny][nx] == 0:
                ny = ny + dy[i]
                nx = nx + dx[i]
            if 0 <= ny < 4 and 0 <= nx < 4 and costMap[ny][nx] > costMap[y][x] + 1:
                costMap[ny][nx] = costMap[y][x] + 1
                queue.append((ny, nx))


# 어떤 카드를 선택하냐에 따라 달라질 수도? 그럼 다 돌아봐야지
# 기존에 뽑았던 카드 위주로 돌림
def dfs(board, r, c, count, hashMap):
    global answer
    n_board = deepcopy(board)
    n_hashMap = deepcopy(hashMap)

    # 지금 뒤집을 카드
    targetNum = n_board[r][c]
    # 카드 뒤집었음
    n_board[r][c] = 0
    (ty1, tx1) = n_hashMap[targetNum][0]
    (ty2, tx2) = n_hashMap[targetNum][1]
    ty, tx = 0, 0
    if ty1 == r and tx1 == c:
        ty = ty2
        tx = tx2
    else:
        ty = ty1
        tx = tx1

    count += bfs(n_board, r, c, ty, tx)
    n_board[ty][tx] = 0
    del n_hashMap[targetNum]
    if checkFinished(n_board):
        answer = min(answer, count)
        return

    #아직 안끝났으면 다음 남아 있는 카드들 돌리는 상황
    for value in n_hashMap.values():
        for ny,nx in value:
            #현재 위치에서 다음 뒤집을 첫 카드 위치로 이동
            cnt = bfs(n_board,ty,tx,ny,nx)
            dfs(n_board,ny,nx,count + cnt,n_hashMap)


def checkFinished(board):
    for y in range(4):
        for x in range(4):
            if board[y][x] != 0:
                return False
    return True