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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/72415

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

문제는 간단하보였지만 구현이 빡셌던 문제이다.

 

처음에는 무지성으로 다 돌리면 되지 않을가 생각했다.

방문해야하는 그림카드가 최대 6쌍이므로 12개이다.

이것으로 조합만들면 12! 이므로 되지 않을까 했는데 4억7천정도되서 시간초과 나지 않을까 해서 이방법은 접었다.

 

그래서 비트마스크를 활용해서 BFS로 해결했다.

비트마스크는 현재 뒤집은 카드를 기록한다.

카드 세트당 2개의 비트를 사용하므로 아무카드도 뒤집지 않은 것까지 포함해서 최대 13비트만 사용하면 된다.

그래서 각 카드에 번호를 부여했다.

이때 각 카드는 서로 세트로 와야해서 1번 카드세트부터 순서대로 번호를 부여했다.

그래서 1번카드 하나는 1, 다른것 2, 2번은 3, 다른건 3 이런식으로 번호를 부여해써 짝꿍을 찾을 때 홀수 짝수로 할수 있게 했다.

 

다음 BFS를 수행하면 된다.

이때 중요한 것이 방문체크이다. 나는 4차원 배열로 사용했다.

[x][y][비트마스크 값][들어온 방향]

         (그렇지 않고 다익스트라나 조작 횟수에 따라 이동할지말지 구별해도 된다.)

 

같은 칸이라도 해당 칸으로 들어오는 방향에 따라 조작 횟수가 달라진다.

이동 방향 순서에 따라 조작 횟수가 다르기 때문에 적은 조작횟수라도 이미 방문했던 칸이어서 방문하지 않는 경우가 생기게 된다.

이를 위해 나는 들어오는 방향으로 구분했다.

그렇지 않고 이동거리가 더 짧은게 오면 이동하게 하거나 다익스트라로 해도 무방하다.

 

일단 해당 카드에서 시작하기 위해 정보를 큐에 넣는다.

큐에 넣는 정보는 다음과 같다.

(x, y, 뒤집은 횟수, 비트마스크 변수, 짝꿍 번호)

아직 아무카드도 뒤집지 않았따면 짝꿍 번호는 -1 이다.

 

만약 시작 자리에 카드가 있다면 해당 카드를 뒤집는 것도 체크해야하므로 추가해서 넣는다.

 

해당 자리의 번호를 가지고 비트마스크 변수를 갱신하고 짝꿍 카드 번호를 구한다.

이는 홀수짝수로 구별가능하게 번호를 부여했다. 홀수면 짝꿍은 +1, 짝수면 짝꿍은 -1이 된다.

 

이제 BFS를 수행하면 되는데 비트마스크 변수의 비트가 0번째 비트 빼고 모두 1이 될때까지 수행하면 된다.

번호가 0인 카드는 없기 때문에 0번째 비트는 항상 0이다.

 

다음 고려 사항은 이동이다.

하나는 한칸만 이동하는 것이고 다른 하나는 다른 카드 혹은 끝칸까지 이동하는 것이다.

 

이것은 한칸 먼저 이동하고 해당 자리에 다른 카드가 있다면 멈추면 되고

빈칸이라면 끝까지 가보면 된다.

 

이동 시 해당 시점에서 카드가 뒤집힌건지 아닌지는 체크해야되는데 이는 비트마스크 변수를 활용하면 된다.

만약 어떤 칸에 0이 아닌 값이라면 비트마스크의 해당 값의 비트가 0이면 뒤집힌거고 아니면 아직 뒤집히지 않은 것이다.

 

만약 비트값이 0000 0110이고 다음칸이 3번 카드라면

1,2번 카드를 뒤집은 상황에서 3번은 아직 뒤집히지 않은 상태이다.

 

이제 짝꿍카드에 도착했는지 혹은 -1인지 혹은 빈칸인지를 구별해서 BFS를 진행하면 된다.

 

그리고 마지막으로 정답은 먼저 도착했다고 가장 작은 값이 아니므로 최솟값이 오도록 갱신하자.

 

설명이 개판이라.. 코드를 보는게 더 낫을 듯 하다.

 

from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def solution(board, r, c):
    global answer
    answer = 9876543210
    board, max_num = renew_board(board)
    visited = [[[[False]*(2 ** max_num) for _ in range(4)] for _ in range(4)] for _ in range(4)]
    bfs(board, r, c, visited, max_num)
    return answer


def bfs(board, sx, sy, visited, max_num):
    global answer
    q = deque()

    if board[sx][sy] > 0:
        num = board[sx][sy]
        nxt_visited_bit = (1 << num)
        nxt = num - 1 if num % 2 == 0 else num + 1
        q.appendleft((sx, sy, 1, nxt_visited_bit, nxt))
    q.appendleft((sx,sy, 0, 0, -1))
    while q:
        x, y, count, visited_bit, target = q.pop()

        if visited_bit == (2**max_num)-2:
            answer = min(answer, count)
            continue
        for d in range(4):
            nx, ny = x, y
            for typ in range(2):
                if typ == 0:
                    nx += dx[d]
                    ny += dy[d]
                else:
                    nx,ny = ctrl_move(nx, ny, d, board, visited_bit)

                if point_validator(nx, ny, visited, visited_bit,d):
                    visited[nx][ny][d][visited_bit] = True
                    num = board[nx][ny]
                    if board[nx][ny] > 0 and visited_bit & (1<<num) == 0:
                        nxt_visited_bit = visited_bit | (1 << num)
                        if target == -1:
                            nxt = num - 1 if num % 2 == 0 else num + 1
                            q.appendleft((nx, ny, count + 2, nxt_visited_bit, nxt))
                        elif target == num:
                            q.appendleft((nx, ny, count + 2, nxt_visited_bit, -1))
                        else:
                            q.appendleft((nx, ny, count + 1, visited_bit, target))
                        break
                    else:
                        q.appendleft((nx, ny, count + 1, visited_bit, target))
                else:
                    break

def ctrl_move(x,y,d,board,visited_bit):
    for _ in range(2):
        x += dx[d]
        y += dy[d]
        if boundray_validator(x, y):
            num = board[x][y]
            if board[x][y] > 0 and visited_bit & (1 << num) == 0:
                break
        else:
            x -= dx[d]
            y -= dy[d]
            break
    return x,y
def boundray_validator(x, y):
    if x < 0 or y < 0 or x >= 4 or y >= 4:
        return False
    return True


def point_validator(x, y, visited, visited_bit,d):
    if not boundray_validator(x, y):
        return False
    elif visited[x][y][d][visited_bit]:
        return False
    return True


def renew_board(board):
    pairs = [[] for _ in range(7)]

    for x in range(4):
        for y in range(4):
            if board[x][y] > 0:
                pairs[board[x][y]].append((x, y))

    new_num = 1
    for pair in pairs:
        for x, y in pair:
            board[x][y] = new_num
            new_num += 1
    return board, new_num