[프로그래머스] 카드 짝 맞추기(BFS, DFS)

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

코딩테스트 연습 - 카드 짝 맞추기

 

bfs와 dfs를 사용하는 문제입니다.

자칫 greedy같은 것을 사용하시는 분들이 있는데 이 방법은 옳은지 틀린지 모르겠으나 예외 케이스가 아마 존재할 것입니다. 실제 올바른 풀이를 먼저 제시하고, testcase는 모두 통과하나 잘못된 풀이도 첨부하겠습니다. 

(블로그 주인장과 다르거나 더 좋은 풀이법이 있을 수 있습니다. 댓글도 환영합니다.)

 

우선 문제부터 요약하면, 

다음과 같이 카드가 배열되어 있을 때

1. enter를 눌러 뒤집거나

2. 방향키를 눌러 1칸 이동시키거나

3-1. ctrl+방향키를 눌러 해당하는 방향에 카드가 있는 지점까지 쭉 이동시키거나 

3-2. ctrl+방향키를 눌러 해당하는 방향에 카드가 쭉 없다면 끝 지점까지 이동시거나

이렇게 총 4가지 옵션으로 카드를 뒤집습니다. 

 

이 때, 같은 카드가 뒤집어 지면 두 카드는 사라지고, 같지 않은 카드가 두개 뒤집히면 다시 두 카드는 원래대로 뒷면을 향하게 뒤집힙니다. 

 

이 때, 모든 카드를 제거하기 위한 최소 횟수를 return하여야 합니다. 

 

즉, solution(board, r, c)에 

board : 현재 카드가 놓인 상태를 나타내는 2차원 배열

r,c : 커서의 처음 위치

가 input으로 주어질 때

 

모든 카드를 몇 옵션 안에 뒤집을 수 있는지 최솟값을 return 하여야 합니다. 

문제가 꽤 기니 궁금하신 분은 위의 홈페이지에 들어가서 문제를 읽어 보고 이해하는 것을 추천합니다. 

 

<Solution-정답> 

아이디어를 간단하게 설명하고, 코드를 기반으로 설명하겠습니다. 

 

우선 A라는 카드를 뒤집게 되면 다음은 무조건 A를 뒤집어야 최솟값이 됩니다. (만약 B를 뒤집는다면, B,A둘다 원상복귀 되고, 시간만 낭비하는 것임) 따라서 A,B,C 3종류의 카드가 4x4 판에 배열되었다고 생각하면, A,B,C를 뒤집는 순서를 고려햐여 각각의 모든 경우에 대한 최소 시간을 구해서 그중 최솟값을 구해야 합니다. 

 

즉 (A,B,C), (A,C,B), (B,A,C), (B,C,A), (C,A,B), (C,B,A) 이렇게 총 6가지 뒤집는 경우 각각에 대한 최솟값을 구하고, 그중에서 최솟값이 결과가 됩니다. 

여기에서 생각 해야하는 것은, A라는 카드가 두개라는 것입니다. 

다음과 같은 상황을 생각해보면, 시작커서에서 바로 [0,0]의 위치인 A로 갈 수 있고, [1,2]의 위치인 A로 갈 수 있습니다. 

위 그림처럼 어느 것을 먼저 뒤집느냐에 따라 횟수가 다르기 때문에 둘다 고려해서 최솟값을 정해주어야 하는 것을 알 수 있습니다. 

 

자 여기까지 이해했다면, 코드를 구현할 수 있습니다. 

1. A,B,C의 순서를 정한다(6가지 모두 탐색) (편의를 위해 A->B->C 순으로 탐색한다고 가정하면) 2-1. 처음 커서에서 [0,0]의 A부터 방문하는 경우에 대해 dfs 2-2. 처음 커서에서 [1,2]의 A부터 방문하는 경우에 대해 dfs

간단하게 설명하면 다음과 같은데 이게 무슨이야기냐 하는 분들을 위해 추가적인 설명을 해보겠습니다. 

 

현재 상황에서 각각의 카드를 key, 위치를 value로 하는 dict를 구성한다고 생각해봅시다. 

d = {'A' : [[0,0],[1,2]], 'B' : [[0,3],[2,1]], 'C' : [[3,0],[3,3]]} 

와 같이 구성됩니다. 그러면 우리가 A->B->C의 순서로 카드를 뒤집는 경우를 생각해보면, 

위의 경우에 대해 8가지 모두 탐색을 해야합니다. 이 과정은 dfs로 구현하였습니다. 

코드의 흐름을 보면, [전의 row 좌표, 전의 column 좌표, board상태, 현재까지 횟수, 카드수]를 계속 pop하며 stack을 통한 dfs로 구현하였습니다. 

 

위의 예시를 토대로 생각해보면, 

가장 처음에는 [0,1,[board 상태], 0,0]이 들어갈 것입니다. 

stack = [[0,1,[board 상태], 0,0]] 에서 stack을 pop 한 뒤에 이제는 A라는 카드를 뒤집어야 합니다. 

1. 현재위치에서 A카드의 위치로 이동하면서 count늘리기 2. A카드 위치에서 또다른 A카드 위치로 이동하면서 count늘리기

이러한 과정이 진행되고 A1,A2카드 이렇게 A카드를 두개가 있다고 생각하면, A1->A2의 순서로 뒤집는 경우, A2->A1의 순서로 뒤집는 경우에 대해 둘다 고려해서 stack에 넣어줍니다. 

 

*추가설명

1. how_many_times라는 함수가 있는데 이 함수는 bfs를 통해 좌표 두개와 현재 board상태를 input으로 받아 현재의 board상태에서 해당하는 좌표간의 이동횟수의 최솟값을 return해줍니다. bfs이기 때문에 가장 처음 목표 위치로 도달하는 경우에 return 하면 됩니다. 

2. 가지치기를 일부 하지 않으면 테스트 케이스에서 3개정도에서 시간초과가 일어납니다. 가지치기는 

            if len(answer_list) != 0 and temp[3] >= min(answer_list):
                continue

이렇게 dfs를 하는 도중 이미 갈수 있는 경우보다 횟수가 큰 것이 나오면 바로 해당하는 부분은 진행하지 않도록 가지치기 합니다. 

 

실제구현은 아래와 같습니다. 독자들의 쉬운 디버깅을 위해 주석은 남겨두었습니다. 

import itertools
from collections import deque
from collections import defaultdict
import copy
mov_r = [0, 0, -1, 1] # right left up down
mov_c = [1, -1, 0, 0]

def outofblock(x, y):
    return x>3 or y>3 or x<0 or y<0

# bfs
def how_many_times(board, current_position, position_to_move): 
    # print(f'current_position, position_to_move : {current_position, position_to_move}')
    # input format : board, [1,0], [0,1]
    q = deque()
    new_current_position = current_position[:]
    new_current_position.append(0)
    q.append(new_current_position) # [1,0,0] 0-> move count

    while q:
        r, c, k = q.popleft()

        if r == position_to_move[0] and c == position_to_move[1]:
            # print(f'return value : {k}')
            return k

        for i in range(4):
            # without ctrl
            new_r = r + mov_r[i]
            new_c = c + mov_c[i]
            if not outofblock(new_r, new_c):
                q.append([new_r, new_c, k+1])

            # with ctrl
            flag = 0
            while(not outofblock(new_r, new_c) and board[new_r][new_c] == 0):
                flag = 1
                new_r += mov_r[i]
                new_c += mov_c[i]
                # print(f'newr, newc = {new_r, new_c}')
            if flag == 1:
                if outofblock(new_r, new_c):
                    q.append([new_r-mov_r[i], new_c-mov_c[i], k+1])
                else:
                    q.append([new_r, new_c, k+1])
    
    # not reachable
    return -1

def solution(board, r, c):
    # print(board)
    d = defaultdict(list)
    for i in range(4):
        for j in range(4):
            if board[i][j] != 0:
                d[board[i][j]].append([i,j])
    d = dict(d)
    card = d.keys()
    nPr = list(itertools.permutations(card, len(card)))

    answer_list = []
    for i in nPr:
        # print("-----------------------")
        # print(i)
        # dfs
        s = [[r,c,board,0,0]] # stack 0,0 -> cnt, numcard
        
        while s:
            temp = s.pop()
            if len(answer_list) != 0 and temp[3] >= min(answer_list):
                continue
            # print(f'temp : {temp}')
            # print(len(card))
            if temp[4] == len(card):
                answer_list.append(temp[3])
                continue

            j = i[temp[4]]
            
            # print(f'j : {j}')
            new_board1 = copy.deepcopy(temp[2])
            new_board2 = copy.deepcopy(temp[2])
            
            # A->B
            time1 = how_many_times(new_board1, [temp[0], temp[1]], d[j][0])
            new_board1[d[j][0][0]][d[j][0][1]] = 0
            time1 += how_many_times(new_board1, d[j][0], d[j][1])
            new_board1[d[j][1][0]][d[j][1][1]] = 0
            # print(f'append_array_value : {[d[j][1][0], d[j][1][1], new_board1, temp[3]+time1+2, temp[4]+1]}')
            s.append([d[j][1][0], d[j][1][1], new_board1, temp[3]+time1+2, temp[4]+1])

            # B->A
            time2 = how_many_times(new_board2, [temp[0], temp[1]], d[j][1])
            new_board2[d[j][1][0]][d[j][1][1]] = 0
            time2 += how_many_times(new_board2, d[j][1], d[j][0])
            new_board2[d[j][0][0]][d[j][0][1]] = 0
            #print(f'append_array_value : {[d[j][0][0], d[j][0][1], new_board2, temp[3]+time2+2, temp[4]+1]}')
            s.append([d[j][0][0], d[j][0][1], new_board2, temp[3]+time2+2, temp[4]+1])

    # print(answer_list)
    return min(answer_list)

또한 문제에서 주어지지 않은 testcase입니다. 

solution([[1, 5, 0, 2], [6, 4, 3, 0], [0, 2, 1, 5], [3, 0, 6, 4]], 0, 0)) # should return 32

아래의 예시는 조금 어려운 예시인데 19가 아닌 18을 return 하여야합니다. 이것을 통과 못해도 프로그래머스에 있는 testcase들은 모두 통과할 수 있습니다. (greedy와 같은 알고리즘을 사용하게 되면 아래의 testcase는 통과하지 못합니다.)

solution([[0, 0, 1, 0], [1, 0, 0, 0], [4, 4, 3, 2], [0, 3, 2, 0]], 2,0) # should return 18

 

<Solution -오답>

testcase는 모두 통과하지만 문제가 있는 코드입니다. 처음 짠 코드인데 설명해보겠습니다. 

코드의 진행이 각각의 카드 즉 A->B->C라는 과정을 거치면, 3부분으로 나누어서 진행됩니다. 

1. 처음위치에서 A1->A2 이렇게 까지 총 횟수를 구한다. 2. 처음위치에서 A2->A1 이렇게 까지 총 횟수를 구한다.  3. 둘중 작은 경우에 대해 처음 위치를 set한다. (즉 1이 적으면 이후의 처음위치는 A1, 반대의 경우 A2) 4. 이제 1-3과정을 A대신 B카드에 대해 반복하고, 마찬가지로 C에대해서도 이 과정을 진행한다.

이렇게 하게 되면, A카드를 뽑고나서 B카드를 뽑기 시작할 때 A1->A2의 순서인지, A2->A1의 순서인지에 따라 B에 영향이 있습니다. 즉 A, B간의 dependency를 가지게 됩니다. 이러면 A의 저러한 과정을 통한 최솟값 + B의 저러한 과정을 통한 최솟값 + C의 저러한 과정을 통한 최솟값이 전체를 최소로 만든다는 보장이 없습니다.(Independent하지 않기 때문)

일종의 Greedy한 알고리즘입니다. 

 

실제 구현은 아래와 같습니다. (이 코드 또한 주석을 남겨두겠습니다.)

import itertools
from collections import deque
from collections import defaultdict
import copy
mov_r = [0, 0, -1, 1] # right left up down
mov_c = [1, -1, 0, 0]

def outofblock(x, y):
    return x>3 or y>3 or x<0 or y<0

# bfs
def how_many_times(board, current_position, position_to_move): 
    # print(f'current_position, position_to_move : {current_position, position_to_move}')
    # input format : board, [1,0], [0,1]
    q = deque()
    new_current_position = current_position[:]
    new_current_position.append(0)
    q.append(new_current_position) # [1,0,0] 0-> move count

    while q:
        r, c, k = q.popleft()

        if r == position_to_move[0] and c == position_to_move[1]:
            # print(f'return value : {k}')
            return k

        for i in range(4):
            # without ctrl
            new_r = r + mov_r[i]
            new_c = c + mov_c[i]
            if not outofblock(new_r, new_c):
                q.append([new_r, new_c, k+1])

            # with ctrl
            flag = 0
            while(not outofblock(new_r, new_c) and board[new_r][new_c] == 0):
                flag = 1
                new_r += mov_r[i]
                new_c += mov_c[i]
                # print(f'newr, newc = {new_r, new_c}')
            if flag == 1:
                if outofblock(new_r, new_c):
                    q.append([new_r-mov_r[i], new_c-mov_c[i], k+1])
                else:
                    q.append([new_r, new_c, k+1])
    
    # not reachable
    return -1

def solution(board, r, c):
    # print(board)
    d = defaultdict(list)
    for i in range(4):
        for j in range(4):
            if board[i][j] != 0:
                d[board[i][j]].append([i,j])
    d = dict(d)
    card = d.keys()
    nPr = list(itertools.permutations(card, len(card)))

    answer_list = []
    for i in nPr:
        initp = [r,c]
        new_board1 = copy.deepcopy(board) # for A->B
        new_board2 = copy.deepcopy(board) # for B->A
        cnt = 0
        # print("-----------------------")
        # print(i)
        for j in i: 
            # print(f'initp : {initp}')
            # A->B
            time1 = how_many_times(new_board1, initp, d[j][0])
            new_board1[d[j][0][0]][d[j][0][1]] = 0
            time1 += how_many_times(new_board1, d[j][0], d[j][1])
            new_board1[d[j][1][0]][d[j][1][1]] = 0
            # B->A
            time2 = how_many_times(new_board2, initp, d[j][1])
            new_board2[d[j][1][0]][d[j][1][1]] = 0
            time2 += how_many_times(new_board2, d[j][1], d[j][0])
            new_board2[d[j][0][0]][d[j][0][1]] = 0
            # eventually new_board 1 and 2 are same
            if time1 <= time2:
                # print(f'time1 : {time1}, time2 : {time2}')
                # print(f'before cnt : {cnt}\n+= time1 :{time1+2}')
                cnt+=(time1+2)
                initp = d[j][1]
            else:
                # print(f'time1 : {time1}, time2 : {time2}')
                # print(f'before cnt : {cnt}\n+= time2 :{time2+2}')
                cnt+=(time2+2)
                initp = d[j][0]
        answer_list.append(cnt)
    # print(answer_list)
    return min(answer_list)

 

실제로 아래의 예시를 넣게 되면, 19가 나와서 틀린 코드입니다. 

solution([[0, 0, 1, 0], [1, 0, 0, 0], [4, 4, 3, 2], [0, 3, 2, 0]], 2,0) # should return 18