프로그래머스 카드 짝 맞추기
문제
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를 만들어서 구해줍니다.
Author And Source
이 문제에 관하여(프로그래머스 카드 짝 맞추기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@josajang98/카드-짝-맞추기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)