카드 짝 맞추기 (72415번) - 프로그래머스 (Programmers)

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

프로그래머스

 

 

프로그래머스 - 카드 짝 맞추기 (72415번)

 

난이도 : Lv 3

알고리즘 : BFS (깊이 우선 탐색)

풀이 소요 시간 : 150 mins

 

 

from itertools import permutations as p
from copy import deepcopy


def solution(board, r, c):
    def bfs(r1, c1, r2, c2):
        v = [[False]*4 for _ in range(4)]
        v[r1][c1] = True
        q = [(r1, c1)]
        d = 0
        while q:
            tmp = []
            for r, c in q:
                if r == r2 and c == c2:
                    return d
                for i in range(4):
                    nr, nc = r+dr[i], c+dc[i]
                    if 0 <= nr < 4 and 0 <= nc < 4 and not v[nr][nc]:
                        tmp.append((nr, nc))
                        v[nr][nc] = True
                    while 0 <= nr < 4 and 0 <= nc < 4:
                        if cur[nr][nc]:
                            if not v[nr][nc]:
                                tmp.append((nr, nc))
                                v[nr][nc] = True
                            break
                        nr += dr[i]; nc += dc[i]
                    else:
                        nr -= dr[i]; nc -= dc[i]
                        if not v[nr][nc]:
                            tmp.append((nr, nc))
                            v[nr][nc] = True
            q = tmp
            d += 1
        return

    
    # ①
    cats = max(max(b) for b in board) + 1
    coords = [[(-1, -1), (-1, -1)] for _ in range(cats)]
    coords[0] = [(r, c), (r, c)]
    for r in range(4):
        for c in range(4):
            if not board[r][c]:
                continue
            i = 0 if coords[board[r][c]][0] == (-1, -1) else 1
            coords[board[r][c]][i] = (r, c)

    dr = [1, -1, 0, 0]
    dc = [0, 0, 1, -1]
    miny = 255
    # ②
    for seq in p(range(1, cats)):
        cur = deepcopy(board)
        cnt1 = cnt2 = s = 0
        for e in seq:
        # ③
            d12, d21 = bfs(*coords[e][0], *coords[e][1]), bfs(*coords[e][1], *coords[e][0])
            cnt1, cnt2 =\
            min( cnt1 + bfs(*coords[s][0], *coords[e][1]), cnt2 + bfs(*coords[s][1], *coords[e][1]) ) + d21,\
            min( cnt1 + bfs(*coords[s][0], *coords[e][0]), cnt2 + bfs(*coords[s][1], *coords[e][0]) ) + d12
            cur[coords[e][0][0]][coords[e][0][1]] = cur[coords[e][1][0]][coords[e][1][1]] = 0
            s = e
        miny = min(miny, cnt1, cnt2)
    # ④
    return miny + 2*(cats-1)

 

 

2021 KAKAO BLIND RECRUITMENT 기출문제이다.

BFS 활용해서 해결했는데, 조건이 상당히 까다로웠다.

 

---

 

 

① 캐릭터 별 좌표를 coords에 저장해둔다.

 

 

 

② 조합을 활용해서 캐릭터를 모두 삭제하는, 모든 경우의 수를 탐색한다.

 

 

 

③ 처음 시작 커서부터 출발해서, 캐릭터를 하나씩 삭제해나간다.

 

먼저 현재까지 최소 조작 횟수를 저장할 cnt를 0으로 초기화한다.

cnt1 = cnt2 = 0

 

캐릭터 a 에서 출발해서 b 로 가는 가능한 경로를 생각해보면,

a1 → b1
a2 → b1
a1 → b2
a2 → b2

이렇게 4가지가 가능하다.

 

이 중, b1으로 도착하는

(cnt1 + a1) → b1
(cnt2 + a2) → b1

중 조작 횟수가 작은 값 하나만 취하고,

여기에 b1 → b2 로 가는 조작 횟수 d12 를 더해주면,

(처음 커서) → b2 로 가는 최소의 조작 횟수를 구할 수 있다.

이를 cnt2 로 업데이트 해준다.

 

마찬가지로, b2로 도착하는

(cnt1 + a1) → b2
(cnt2 + a2) → b2

중 조작 횟수가 작은 값 하나만 취하고,

여기에 b2 → b1 로 가는 조작 횟수 d21 을 더해주면,

(처음 커서) → b1 로 가는 최소의 조작 횟수를 구할 수 있다.

이를 cnt1 으로 업데이트 해준다.

 

 

 

④ 이렇게 모든 조합의 경우에 대해서 조작 횟수를 구하고,

그 중 최솟값에 enter 키 조작 횟수를 더해서 반환한다.