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

문제

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

코드

python

from itertools import permutations
from collections import defaultdict, deque
from copy import deepcopy

d = [[0, 1], [0, -1], [1, 0], [-1, 0]]


def bfs(cy, cx, ty, tx, board):
    q = deque()
    q.append((cy, cx))
    dist = [[0]*4 for _ in range(4)]
    dist[cy][cx] = 1
    while q:
        y, x = q.popleft()

        for dy, dx in d:
            ny = y+dy
            nx = x+dx
            if 0 <= ny < 4 and 0 <= nx < 4:
                if dist[ny][nx] == 0:
                    dist[ny][nx] = dist[y][x]+1
                    q.append((ny, nx))

                if dy == 0:
                    while 0 <= nx < 4 and board[ny][nx] == 0:
                        nx += dx
                    if not 0 <= nx < 4:
                        nx -= dx
                else:
                    while 0 <= ny < 4 and board[ny][nx] == 0:
                        ny += dy
                    if not 0 <= ny < 4:
                        ny -= dy
                if dist[ny][nx] == 0:
                    dist[ny][nx] = dist[y][x]+1
                    q.append((ny, nx))
    return dist[ty][tx]


def dfs(y, x, d, cost, board, arr):
    global answer
    if d == len(pos):

        answer = min(answer, cost)
        return
    temp = deepcopy(board)
    y1, x1 = pos[arr[d]][0]
    y2, x2 = pos[arr[d]][1]
    v1 = bfs(y, x, y1, x1, temp)+bfs(y1, x1, y2, x2, temp)
    v2 = bfs(y, x, y2, x2, temp)+bfs(y2, x2, y1, x1, temp)

    temp[y1][x1] = 0
    temp[y2][x2] = 0
    dfs(y2, x2, d+1, cost+v1, temp, arr)
    dfs(y1, x1, d+1, cost+v2, temp, arr)


def solution(board, r, c):

    global pos, answer
    answer = 1e9
    pos = defaultdict(list)
    for i in range(4):
        for j in range(4):
            if board[i][j] == 0:
                continue
            pos[board[i][j]].append((i, j))

    for arr in list(permutations(range(1, len(pos)+1), len(pos))):
        dfs(r, c, 0, 0, board, arr)

    return answer

cpp

#include <string>
#include <vector>
#include<algorithm>
#include <queue>

using namespace std;
int maxV = 0;
vector<int> answers;
int visit[7] = { 0, };
vector<vector<int>> location[7];


int bfs(int r, int c, int r1, int c1, vector<vector<int>> board) {
    int result = 0;
    vector<vector<int>> map(4, vector<int>(4, 0));
    map[r][c] = 1;

    queue<pair<int, int>> q;
    q.push({ r,c });
    int dir[4][2] = { {0,1},{1,0},{-1,0},{0,-1} };

    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
      
        for (int i = 0; i < 4; i++) { //동서남북 방향키 1씩 움직이는 상황 
            int tY = y+ dir[i][0];
            int tX = x+ dir[i][1];
            if (0 > tY || tY >= 4 || 0 > tX || tX >= 4 || map[tY][tX] != 0) continue;
            map[tY][tX] = map[y][x] + 1;
            q.push({ tY,tX });
        }
        for (int i = 0; i < 4; i++) { //동서남북 컨트롤 + 방향키로 움직이는 상황 
            int tY = y;
            int tX = x;
            while (0 <= tY && tY < 4 && 0 <= tX && tX < 4) {
                tY += dir[i][0];
                tX += dir[i][1];
                if (!(0 <= tY && tY < 4 && 0 <= tX && tX < 4)||board[tY][tX] != 0) break;
            }
            
            if (!(0 <= tY && tY < 4 && 0 <= tX && tX < 4)) {
                tY -= dir[i][0];
                tX -= dir[i][1];
            }
            
             if (map[tY][tX]!=0)continue;
            map[tY][tX] = map[y][x] + 1;
            q.push({ tY,tX });
        }

    }

    
    return map[r1][c1] - map[r][c];
}

void dfs(int d, int sum, int r, int c, vector<vector<int>> board) {
    if (d == maxV) {
        answers.push_back(sum);
        return;
    }
    for (int i = 1; i <= maxV; i++) {
        if (visit[i] == 1) continue;
        visit[i] = 1;
        int b1_y = location[i][0][0];
        int b1_x = location[i][0][1];
        int b2_y = location[i][1][0];
        int b2_x = location[i][1][1];
        int value1=bfs(r, c, b1_y, b1_x, board) + bfs(b1_y, b1_x, b2_y, b2_x, board) + 2;
        int value2=bfs(r, c, b2_y, b2_x, board) + bfs(b2_y, b2_x, b1_y, b1_x, board) + 2;
        vector<vector<int>> temp = board;
        temp[b1_y][b1_x] = 0;
        temp[b2_y][b2_x] = 0;

        dfs(d + 1, sum + value1, b2_y, b2_x, temp);
        dfs(d + 1, sum + value2, b1_y, b1_x, temp);
        visit[i] = 0;
    }
}

int solution(vector<vector<int>> board, int r, int c) {
    int answer = 0;
   
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (board[i][j] != 0) {
                location[board[i][j]].push_back({ i,j });
                maxV = max(maxV, board[i][j]);
            }
        }
    }
    dfs(0, 0, r, c, board);
    answer=*min_element(answers.begin(), answers.end());
    return answer;
}

풀이

풀이법은 bfs와 dfs를 사용해서 모든 경우의 수를 다 탐색하는 것입니다. 예를 들어서 블록의 종류가 3개라면

1 -> 2 -> 3

1 -> 3 -> 2

2 -> 1 -> 3

2 -> 3 -> 1

3 -> 1 -> 2

이렇게 모든 경우를 다 탐색하는데 이 때 블록의 한쌍이 2개이기 때문에 1번째 블록을 먼저 지우고 2번째 블록을 지우는 경우와 2번째 블록을 지우고 1번째 블록을 지우는 경우까지 전부 생각해서 구현해주면 됩니다 그리고 블록간의 거리는 문제에서 주어진 조건으로 bfs를 만들어서 구해줍니다.