[C++로 풀이] 카드 짝 맞추기 (순열 속 순열, 완전탐색, DFS, BFS, DP)⭐⭐⭐
카테고리: Programmers
태그: Coding Test Algorithm
📌 카드 짝 맞추기
난이도 ⭐⭐⭐
🚀 문제
🚀 내 풀이
💡 어떻게 풀이할 것인가
키 조작 횟수의 최소값 을 구하는 것이기 때문에, 같은 그림의 카드를 바로 바로 한번에 찾는다고 가정하고 문제를 풀이하면 그게 바로 최소의 조작 횟수 “후보”가 된다. 예를 들어 라이언 카드를 뒤집은 상태면 다른 카드를 뒤집어 실패하지 않고, 나머지 라이언 카드를 곧 바로 찾아 뒤집어 두 카드를 제거한다고 가정한다. 즉, 시행착오가 없다고 가정함.
📌 선택한 카드들의 “순열”
어떤 카드를 먼저 선택하느냐에 따라 조작 횟수가 달라지므로 순열 과 관련된 문제이다. 화면도 4x4 크기에다 카드 종류와 개수도 10 개도 안되는 입력 크기이므로 완전 탐색을 통해 카드를 선택하는 모든 순열을 구한 후 그 순열 별로 총 조작횟수를 구한다. 그 중 가장 작은 조작 횟수를 답으로 도출하면 된다.
- 두 가지의 순열을 고려해야 한다.
- 1️⃣ 카드 종류의 순열 (현재의 화면내에서의 카드 종류가 n 개라면
n!)- 카드가 종류를 선택하는 순서에 따라 조작 횟수가 달라지므로 카드 종류에 따른 순열을 고려해야 한다.
- A, B, C 이렇게 3 가지 종류의 카드가 있다면 ABC, ACB, BAC, BCA, CAB, CBA 이렇게
3! = 6가지의 선택 순서가 존재할 수 있다.
- A, B, C 이렇게 3 가지 종류의 카드가 있다면 ABC, ACB, BAC, BCA, CAB, CBA 이렇게
- 카드가 종류를 선택하는 순서에 따라 조작 횟수가 달라지므로 카드 종류에 따른 순열을 고려해야 한다.
- 2️⃣ 같은 카드 끼리의 순열
2!- 문제에서 같은 카드는 2 개씩만 들어있다고 언급을 하고 있다.
- 같은 카드 내에서도 2 가지 순서가 있을 수 있다. 이 문제는 같은 카드를 찾아내면 제거해야 하는데, 같은 종류의 두 카드 중에서도 어떤걸 먼저 선택하느냐에 따라 조작 횟수가 달라지게 된다. 같은 종류의 두 카드도 서로 위치가 제각각 다르기 떄문이다.
- 키 조작 횟수의 최소값을 구하는 것이기 때문에 같은 그림의 카드는 곧 바로 찾아내 제거할 것이라고 위에서 전제하였다. 그렇기 때문에
2n!가 되지는 않는다. 즉, 4 가지 종류의 카드가 있다면 같은 종류인 두 카드도 서로 다른 존재라고 보기 떄문에 총8!가지 순열이 있다고 생각할 수도 있는데 그렇지 않다. 같은 그림의 카드는 바로 찾아낼 것이라고 전제하였기 때문에 (A카드끼리의 순열) 👉 (B카드끼리의 순열) 👉 (C카드끼리의 순열) 이런식으로 순열이 정해져야 하기 때문이다. 즉, 반드시 같은 종류의 카드끼리 뭉쳐서 B1 B2 A2 A1 C2 C1 이런 순열이어야 한다는 얘기다. A1 B2 B1 A2 C2 C1 이런 뒤죽 박죽이 아니라! (이 경우는 8! 이 맞겠지만..)
- 1️⃣ 카드 종류의 순열 (현재의 화면내에서의 카드 종류가 n 개라면
- 따라서 한 화면 내에
n개 종류의 카드가 있다면, 카드를 선택하는 모든 순서는 최대 \(n! × (2!)^{n}\) 개의 순서로 짤 수 있다.- A, B 이렇게 2 가지 종류의 카드가 있다면 2! × 2!^2 = 8 가지의 순서가 있을 수 있다.
- a1-a2-b1-b2
- a1-a2-b2-b1
- a2-a1-b1-b2
- a2-a1-b2-b1
- b1-b2-a1-a2
- b1-b2-a2-a1
- b2-b1-a1-a2
- b2-b1-a2-a1
- A, B 이렇게 2 가지 종류의 카드가 있다면 2! × 2!^2 = 8 가지의 순서가 있을 수 있다.
크게 1️⃣ 카드 종류의 순서(n!), 작게는 2️⃣ 같은 카드 종류 내에서의 순서(2!) 로 나눌 수 있다. 순열의 원소들도 순열인.. 순열 속 순열 문제라고 볼 수 있을 것 같다.
- 순열을 구하기 위한 방법
- 1️⃣ DFS 재귀호출
- 2️⃣ next_permutation 으로 카드 종류의 순서를 구한 후, 해당 카드 종류 순서 내에서 같은 카드 종류 내에서의 순서를 고려하여 최소 조작 횟수를 테이블에 저장해나가는 DP 사용
두 풀이 다 해설할 것이다 :)
📌 조작 횟수
키 조작 횟수의 최소값 을 구하는 것이기 때문에, 카드에서 다른 카드로 이동할 때 필요한 조작 횟수도 최소여야 한다는 의미이다. 최단 경로를 구하는 알고리즘이 생각이난다! 게다가 한번 이동할 때 조작횟수는 공통적으로 1 이다. 즉, 가중치가 모두 동일한 것이나 마찬가지이므로 지점 간의 최소 조작 횟수를 구하기 위해선 BFS 가 제격이다.
- 현재 위치에서 이동 가능 한 곳 (👉 큐에 삽입하여 다음에 방문할 곳으로 예약할 곳들)
- 방향키
- 위 한칸
- 아래 한칸
- 오른쪽 한칸
- 왼쪽 한칸
- Ctrl + 방향키 (한번에 이동할 수 있다.)
- 위 쪽으로 가장 가까운 카드가 있는 곳. 없다면 가장 위 칸.
- 아래 쪽으로 가장 가까운 카드가 있는 곳. 없다면 가장 아래 칸.
- 오른 쪽으로 가장 가까운 카드가 있는 곳. 없다면 가장 오른쪽 칸.
- 왼 쪽으로 가장 가까운 카드가 있는 곳. 없다면 가장 왼쪽 칸.
- 방향키
- Enter 로 각 카드를 뒤집는 것도 한 번의 조작 횟수로 치기 때문에 이것은 그냥 두 카드 사이에 필요한 조작횟수를 모두 구한 후
+ 2만 해주면 된다.
🔥 DFS + BFS 사용한 풀이 ⭕
내가 제출하여 통과했던 풀이이다. 근데 이 풀이는 같은 종류의 카드가 2 개씩 있다고 제한한 것이 아닌, 같은 종류의 카드가 여러개일 수도 있다고 가정하고 푼 풀이이다. 문제에선 “1 부터 6까지의 자연수는 2개씩 들어있으며” 로써 같은 카드는 딱 2개만 있다고 언급을 한 셈인데, 내가 문제를 꼼꼼히 읽지 않아서 생긴 삽질..ㅠㅠㅠ 문제를 다 풀고나서 다른 사람들 풀이를 보니 간단하게 푸셨길래 그제서야 깨달았다.. 그래서 같은 카드 내에서의 순열을 구할 때 같은 카드끼리의 방문 체크를 따로 두어 아직 같은 종류의 카드 내 모든 카드가 선택이 다 된게 아니면 해당 종류의 카드 선택을 또 할 수 있도록 짰다. 또한 순열 속 순열의 느낌을 살리고자..ㅋㅋ 같은 카드 내에서의 순열을 구하는 것도 따로 재귀함수를 두어, 재귀 함수를 2 개 사용하였기 때문에 복잡하고 그닥 깨끗하지 않은 풀이이다. 혹시 코드를 참고하기 위해 이 글을 읽고 계신 분이라면 이 풀이 말고 그 밑에 같은 카드는 2개씩만 있다는 제한 사항을 반영하고 깔끔하게 정리한 두번째 코드를 참고할 것을 추천한다.
[6, 6, 6, 0]
[6, 6, 6, 0]
[6, 0, 0, 0]
[6, 0, 3, 3]
그래서 이런 케이스도 내 풀이론 통과된다.. ㅎㅎㅠ A2 A1 B1 B2 A4 A3 도 가능하도록 풀었다..
#include <string>
#include <vector>
#include <queue>
using namespace std;
#define INF 9999
int n = 0; // 선택하는 모든 카드 쌍의 개수 (카드가 화면 내에 10개라면 n = 5)
int answer = 0;
struct Pos {
int r;
int c;
};
int dirR[] = { 0, 0, -1, 1 };
int dirC[] = { 1, -1, 0, 0 };
vector<vector<Pos>> allCard(7); // 카드 종류 별 위치(Pos) 저장. 인덱스와 카드 종류 동일.
vector<bool> numOfCard_visited(7); // 카드 종류 별 방문 체크. 인덱스와 카드 종류 동일.
vector<vector<bool>> singleCard_visited(7); // 한장 한장씩 모든 카드 별 방문 체크. 인덱스와 카드 종류 동일.
// 전방 선언 (BigDFS 에서도 SmallDFS 가 쓰이고 SmallDFS 에서도 BigDFS 가 쓰여서 전방 선언이 필요했음 ㅠ)
void SmallDFS(vector<vector<int>> board, vector<Pos> sameCards, int cardNum, Pos card, int dist, int small_depth, int big_depth);
int BFS(vector<vector<int>> board, Pos startCard, Pos destCard);
// n 결정 (하나의 순서 내에서의 카드 쌍 개수)
// board에서 allCard 카드 종류별 위치 저장
// singleCard_visited 카드 종류별 다른 크기로(내가 같은 카드가 4개 이상일 수도 있다고 가정하고 문제를 풀었기 때문에..ㅠㅠ) 일차원 벡터 할당
void Categorize(vector<vector<int>> board) {
for (int i = 0; i < board.size(); ++i) {
for (int j = 0; j < board[i].size(); ++j) {
if (board[i][j] != 0) {
allCard[board[i][j]].push_back({ i, j });
n++;
}
}
}
n /= 2;
for (int i = 0; i < allCard.size(); ++i) {
vector<bool> v(allCard[i].size());
singleCard_visited[i] = v; // 카드 종류 별 카드 개수 사이즈만큼
}
}
// 카드 조작 횟수 구하기 (시작점 startCard, 목적지 destCard)
int BFS(vector<vector<int>> board, Pos startCard, Pos destCard) {
queue<Pos> q;
vector<vector<bool>> checked(4, vector<bool>(4));
vector<vector<int>> dist(4, vector<int>(4));
q.push(startCard);
checked[startCard.r][startCard.c] = true; // 모든 위치별 예약 체크
dist[startCard.r][startCard.c] = 0; // 모든 위치별 최소 조작횟수를 담음
while (!q.empty()) {
// 방문
int nowR = q.front().r;
int nowC = q.front().c;
q.pop();
/* 갈 수 있는 곳 예약, 거리 업뎃 */
// 1. 방향키
for (int i = 0; i < 4; ++i) { // 상하좌우 별
int nextR = nowR + dirR[i];
int nextC = nowC + dirC[i];
if (nextR < 0 || nextC < 0 || nextR >= 4 || nextC >= 4)
continue;
if (checked[nextR][nextC])
continue;
q.push({ nextR, nextC });
checked[nextR][nextC] = true;
dist[nextR][nextC] = dist[nowR][nowC] + 1;
}
// 2. Ctrl + 방향키 (한번에 끝으로, 혹은 가장 가까운 카드로 이동 가능)
for (int i = 0; i < 4; ++i) { // 상하좌우 별
int nextR = nowR;
int nextC = nowC;
bool found = false;
// 가장 가까운 카드를 찾거나 혹은 끝에 도달할 때 까지 쭉쭉 한칸씩 이동
while (!found) {
if (nextR + dirR[i] < 0 || nextC + dirC[i] < 0 || nextR + dirR[i] >= 4 || nextC + dirC[i] >= 4) // 끝에 도달하였다면
break;
if (board[nextR + dirR[i]][nextC + dirC[i]] != 0) // 가장 가까운 카드를 찾았다면
found = true;
nextR += dirR[i];
nextC += dirC[i];
}
if (checked[nextR][nextC])
continue;
q.push({ nextR, nextC });
checked[nextR][nextC] = true;
dist[nextR][nextC] = dist[nowR][nowC] + 1;
}
}
return dist[destCard.r][destCard.c]; // 목적지의 최소 조작횟수 리턴
}
// 카드 종류의 순서 결정
void BigDFS(vector<vector<int>> board, Pos card, int dist, int small_depth, int big_depth) {
// 종료 조건 : 화면 내 모든 카드를 선택함 (모든 카드 짝짓기 완성)
// 최종 카드 선택 순서가 정해진 것이므로 여태까지의 조작 횟수와 비교하여 answer 업데이트
if (big_depth == n) {
if (dist < answer)
answer = dist;
return;
}
// 카드의 종류는 최대 6개
for (int i = 1; i <= 6; ++i) {
if (allCard[i].size() == 0) // 현재 화면에 없는 종류는 넘어감~
continue;
if (numOfCard_visited[i] == false) { // 현재 만들고 있는 카드 종류 순서 내에서 이미 선택이 모두 완료된(모두 방문된) 카드가 아니라면
vector<Pos> sameCards = allCard[i]; // i번 카드들의 위치를 담은 벡터 (같은 종류 카드들의 위치)
vector<bool>& sameCard_visited = singleCard_visited[i]; // i번 카드들의 방문 체크를 할 벡터
SmallDFS(board, sameCards, i, card, dist, 0, big_depth);
// 복원 👉 순열에서 가장 중요한 부분! 이 for문 내에서 다음 카드로 뻗어나가는 순서에서 이제 해당 카드도 다시 선택이 될 수 있어야 하기 때문이다.
numOfCard_visited[i] = false; // 방문 체크 해제
}
}
}
// 같은 카드 내에서 2 개 선택하고 순서 결정
// cardNum : 현재 카드 종류
// dist : 현재까지 구한 조작횟수
void SmallDFS(vector<vector<int>> board, vector<Pos> sameCards, int cardNum, Pos card, int dist, int small_depth, int big_depth) {
// 2 개가 모두 선택되었다면 이제 선택할 카드 종류 선택하러 가야하므로 BigDFS 호출
if (small_depth == 2) {
dist += 2; // 두 카드를 Enter 누르면서 발생한 조작횟수 + 2 더해주기
// 현재 이 카드 종류의 모든 카드를 사용했는지 검사해준다. 모두 사용했다면 numOfCard_visited[cardNum] = true
//아직 선택 안된 카드들이 있다면 (내가 같은 종류의 카드가 4 개 이상 있을 수 있다고 가정하고 작성한 코드이기 때문에 ㅠㅠ) 해당 카드 종류의 방문 체크는 하지 않는다. BigDFS 에서 또 선택될 수 있도록 하기 위하여!
// 예를 들어 A1-A3 한 후 나중에 또 A4-A5 이런식으로 선택될 수 있도록
bool flag = true;
for (int i = 0; i < singleCard_visited[cardNum].size(); ++i) {
if (singleCard_visited[cardNum][i] == false) {
flag = false;
break;
}
}
if (flag)
numOfCard_visited[cardNum] = true;
// 다음 카드 종류 선택하러...
BigDFS(board, card, dist, 0, big_depth + 1);
return;
}
// 같은 종류 카드 내에서의 카드 선택
// BigDFS 에서 선택한 종류의 카드들 중에서 2 개 순열
// 현재 종류의 카드가 m 개 있다고 할 떄 mP2 순열
for (int i = 0; i < sameCards.size(); ++i) {
if (singleCard_visited[cardNum][i] == false) {
singleCard_visited[cardNum][i] = true; // 방문 체크 (같은 종류 카드 내에서의 방문 체크)
Pos nextCard{ sameCards[i].r, sameCards[i].c }; // 선택된 카드
int newDist = dist + BFS(board, card, nextCard); // 현재 카드에서 선택된 카드로 가는 조작 횟수
board[sameCards[i].r][sameCards[i].c] = 0; // 카드 제거하기 (다음 재귀호출, 즉 이어서 선택하는 카드들에게도 영향을 미쳐야 함. 카드가 제거 되었으니 BFS 를 통한 조작횟수 측정에도 영향을 미친다.)
SmallDFS(board, sameCards, cardNum, nextCard, newDist, small_depth + 1, big_depth); // 같은 종류 내 다른 카드 선택하러~
// 복원 👉 순열에서 가장 중요한 부분! 이 for문 내에서 다음 카드로 뻗어나가는 순서에서 이제 해당 카드도 다시 선택이 될 수 있어야 하기 때문이다.
board[sameCards[i].r][sameCards[i].c] = cardNum; // 제거한 카드 다시 돌려놓기
singleCard_visited[cardNum][i] = false; // 방문 체크 해제
}
}
}
int solution(vector<vector<int>> board, int r, int c) {
answer = INF;
n = 0;
Categorize(board);
Pos start{ r, c }; // 예제에서 주어진 커서의 처음 위치
BigDFS(board, start, 0, 0, 0);
return answer;
}
- SmallDFS 👉 같은 종류의 카드 내에서의 순서 결정
- BigDFS 👉 카드 종류별 순서 결정 (중복 순열 느낌으로.. 아직 같은 종류의 카드 내에서 모든 카드가 다 선택된게 아니면 또 그 종류의 카드를 호출할 수 있도록 하였다.)
- BFS 👉 카드 종류가 결정될 때마다 두 카드 사이에서의 “조작 횟수”를 구함
A1,A2,A3,A4,B1,B2,C1,C2 이렇게 각각 4,2,2 장 있는 3개 종류의 카드가 있다면 수 많은 순서 중 하나의 순서를 만들어내기까지의 과정은 다음과 같다.
- 두 카드가 선택될 때마다 두 카드 사이의 조작횟수는 그때 그떄마다 BFS 를 통해 구해놓고 누적합 하기로 한다.
- 먼저 BigDFS 을 통해 이번에 선택할 “카드 종류”를 결정한다. A 카드를 선택했다고 가정하겠다.
- 카드 종류를 선택했으면 이 종류에서 2 개를 선택하기 위하여 SmallDFS 를 호출한다.
- 그리고 SmallDFS 을 통해 A 카드들 내에서 해당 순서 내에서 아직 선택 안된 2 개를 고르고 이 2 개의 순서를 재귀호출로 결정한다.
- A 카드들들이 현재 경로(= 현재 만들어나가는 중인 순서)에서 모두 선택 되었다면 A 카드는 모두 썼다고 방문 처리를 해준다. 그래야 BigDFS 에서 카드 종류를 선택할 때 이를 고려할 수 있다. A 카드는 4 개 이상일 수도 있다고 오해하고 푼..ㅠㅠ 풀이이기 때문에 만약 해당 카드가 아직 전부 선택이 안됐다면 A 카드 중 나머지 2 개가 또 선택될 수 있어야 하므로 이떈 방문체크를 해주지 않는다.
- SmallDFS 에서 조작 횟수를 구한다.
- 그리고 다음 종류의 카드 또 선택하러 BigDFS 를 호출한다.
- BigDFS 의 종료 조건은 화면 내의 모든 카드를 선택했을 때이다. 즉, 순서 하나가 완전히 결정되었을 때!
- 종료시 현재 순서동안 여태까지 구했던 총 조작횟수를 현재까지 구한 최소 조작횟수와 비교하면 된다.
BigDFS 속에서 SmallDFS 가 호출되고 또 SmallDFS 가 2 번 깊이로 들어가면 또 BigDFS 가 호출되고 카드 종류가 결정되면 또 SmallDFS 속으로 들어가고.. 이런식의 복잡한 호출을 설계했다..ㅠㅠ
- “출발지(r, c) -> A2위치 -> A1위치 -> C2위치 -> C1위치 -> A3위치 -> A4 위치”
- 위와 같은 식으로 순서들이 결정될 것이다.
🔥 더 깔끔한 다른 풀이 해설! ⭕
위에 있는 내 풀이와 다르게, 1️⃣ 재귀함수를 하나만, 2️⃣ 같은 종류의 카드는 딱 2개만. 을 고려한 풀이이다.
#include <string>
#include <vector>
#include <queue>
using namespace std;
#define INF 987654321
struct Pos {
int row;
int col;
};
vector<vector<int>> Board;
int D[4][2] = { { -1, 0 }, {1, 0}, {0, -1}, {0, 1} }; // 상,하,좌,우
int bfs(Pos start_card, Pos dest_card) {
bool checked[4][4] = { false };
int dist[4][4] = { 0 }; // 조작 횟수
queue<Pos> q;
checked[start_card.row][start_card.col] = true;
dist[0][0] = 0;
q.push(start_card);
while (!q.empty()) {
Pos now_card = q.front();
q.pop();
if (now_card.row == dest_card.row && now_card.col == dest_card.col)
return dist[dest_card.row][dest_card.col];
for (int i = 0; i < 4; ++i) {
int next_row = now_card.row + D[i][0];
int next_col = now_card.col + D[i][1];
// 방향키 이동
if (next_row < 0 || next_row >= 4 || next_col < 0 || next_col >= 4) continue;
if (!checked[next_row][next_col]) {
checked[next_row][next_col] = true;
dist[next_row][next_col] = dist[now_card.row][now_card.col] + 1;
q.push({ next_row, next_col });
}
// Ctrl 이동
for (int j = 0; j < 2; ++j) { // 위에서 방향키를 통해 한칸 이동한 상태이기 때문에 4x4 크기이므로 최대 2칸 더 갈 수 있다. (이미 한칸 온 상태이므로)
if (Board[next_row][next_col] != 0) break; // 다른 카드 만났다면
if (next_row + D[i][0] < 0 || next_row + D[i][0] >= 4 || next_col + D[i][1] < 0 || next_col + D[i][1] >= 4) break; // 끝에 도달했다면
next_row += D[i][0];
next_col += D[i][1];
}
if (!checked[next_row][next_col]) {
checked[next_row][next_col] = true;
dist[next_row][next_col] = dist[now_card.row][now_card.col] + 1;
q.push({ next_row, next_col });
}
}
}
return INF;
}
int permutate(Pos start_card) {
int ret = INF;
for (int num = 1; num <= 6; ++num) { // 카드는 1~6 있을 수 있다. 카드 넘버별 저장
vector<Pos> card; // 종류별 같은 카드들 저장할 곳, 크기 2 가 될 것.
for (int i = 0; i < 4; ++i)
for (int j = 0; j < 4; ++j)
if (Board[i][j] == num)
card.push_back({ i, j });
if (card.empty()) continue; // num이 이미 제거된 카드 or 혹은 없는 카드
// 같은 카드를 순회하는 2가지 방법
int one = bfs(start_card, card[0]) + bfs(card[0], card[1]) + 2; // start_card -> card[0] -> card[1] 순서로 선택할 때의 조작 횟수
int two = bfs(start_card, card[1]) + bfs(card[1], card[0]) + 2; // start_card -> card[1] -> card[0] 순서로 선택할 때의 조작 횟수
// 카드 제거
for (int i = 0; i < 2; ++i)
Board[card[i].row][card[i].col] = 0;
// 가장 작은게 ret 에 담기게 된다. (최대 12번 비교)
ret = min(ret, one + permutate(card[1])); // card[0] -> card[1] 을 끝낸 후 이제 다른 카드 순회. card[1] 이 다음의 start_card 가 된다.
ret = min(ret, two + permutate(card[0])); // card[1] -> card[0] 을 끝낸 후 이제 다른 카드 순회. card[0] 이 다음의 start_card 가 된다.
// 제거한 카드 복원 (다음 num 에서 뻗어나가는 순열에서 선택될 수 있어야 하므로)
for (int i = 0; i < 2; ++i)
Board[card[i].row][card[i].col] = num;
}
if (ret == INF) // 이 재귀 호출에서 ret 가 INF 일 때는 모든 카드가 제거됐을 때이다! 즉, 모든 카드가 push_back 되지 못하여 if (card.empty()) continue; 에 걸리게 되어서 ret 이 한번도 업뎃되지 못한 경우다. 모든 카드가 제거된 상태일 때는 재귀 호출 종료
return 0; // 0 리턴. 👉 즉, 돌아오고나면 one + permutate(card[1]) = one + 0 = one 이 되는 것이나 마찬가지이다.
return ret;
}
int solution(vector<vector<int>> board, int r, int c) {
Board = board;
int answer = permutate({ r, c });
return answer;
}
풀이는 위 유튜브 영상을 참고하였다.
- DFS
- 최소 조작 횟수를 리턴값으로 받는다.
- 카드를 모두 선택하여 순서를 완성했을 떄는 0 을 리턴하는게 흥미롭다.
- 0 을 리턴하고 돌아가면
ret = min(ret, two);,ret = min(ret, one);이 되는 것이나 마찬가지이기 때문에 같은 종류의 두 카드 중 어떤 것을 먼저 방문할지에 관한 순서 2! 가지 방법 중 최소 조작횟수가ret에 최종적으로 담기게 된다.
- 0 을 리턴하고 돌아가면
ret은 매 호출마다 새롭게 선언되어 INF 로 초기화 되는 변수이다.- 해당 재귀 단계(몇 번째로 선택된 카드 종류인지)내에서의 지역변수다. 즉, for 문으로 순회하는 해당 재귀 단계에 모든 카드들이 시작 루트가 될 때에서의 최소값이 for문을 돌면서
ret에 모이게 된다.
- 해당 재귀 단계(몇 번째로 선택된 카드 종류인지)내에서의 지역변수다. 즉, for 문으로 순회하는 해당 재귀 단계에 모든 카드들이 시작 루트가 될 때에서의 최소값이 for문을 돌면서
- 되돌아오는 과정에서는
ret을 리턴하게 된다.- 따라서 윗 재귀 단계에서도 이
ret을 리턴받으므로 최종적으로permutate({ r, c })은 모든 경우의 수의 최소 조작 횟수를 리턴할 수 있게 된다.
- 따라서 윗 재귀 단계에서도 이
- BFS
- 어차피 “Ctrl + 방향키”도 상하좌우별로 진행되기 때문에 내 위의 풀이와 다르게 상하좌우 “방향키” 예약할 때 함께 진행하게 된다.
- 습관처럼 별 생각없이 방문한 위치인지를 체크할 때 아래와 같이 작성했었는데, 아래와 같이 코드를 작성하면 몇몇 테스트케이스는 통과할 수 없었다. 그 이유는 방향키로 갈 수 있는 상하좌우 한칸은 방문한 곳일지 몰라도 Ctrl + 방향키로는 갈 수 있기도 하기 떄문이다. 예를 들면 오른쪽 방향이면 오른쪽 한칸(방향키)는 방문한적 있어 큐에 삽입 못한다 하더라도 맨 오른쪽 끝은 방문한적 없어 큐에 삽입될 수도 있기 때문이다. 그래서 평소처럼 방문한 위치를 거를 때 아래와 같이 코드를 작성했는데 이러면 방향키로 갈 수 있는 곳이 방문되었다면 그냥
continue되버리니 Ctrl + 방향키로 갈 수 있는 방향인지를 따져볼 수가 없었다. 따라서 아래의 두 번째 코드로 바꾸니 해결 되었다. (위 유튜브에서 소개한 코드와 똑같이)if (checked[next_row][next_col]) continue; checked[next_row][next_col] = true; dist[next_row][next_col] = dist[now_card.row][now_card.col] + 1; q.push({ next_row, next_col });if (!checked[next_row][next_col]) { checked[next_row][next_col] = true; dist[next_row][next_col] = dist[now_card.row][now_card.col] + 1; q.push({ next_row, next_col }); }
- 습관처럼 별 생각없이 방문한 위치인지를 체크할 때 아래와 같이 작성했었는데, 아래와 같이 코드를 작성하면 몇몇 테스트케이스는 통과할 수 없었다. 그 이유는 방향키로 갈 수 있는 상하좌우 한칸은 방문한 곳일지 몰라도 Ctrl + 방향키로는 갈 수 있기도 하기 떄문이다. 예를 들면 오른쪽 방향이면 오른쪽 한칸(방향키)는 방문한적 있어 큐에 삽입 못한다 하더라도 맨 오른쪽 끝은 방문한적 없어 큐에 삽입될 수도 있기 때문이다. 그래서 평소처럼 방문한 위치를 거를 때 아래와 같이 코드를 작성했는데 이러면 방향키로 갈 수 있는 곳이 방문되었다면 그냥
- 어차피 “Ctrl + 방향키”도 상하좌우별로 진행되기 때문에 내 위의 풀이와 다르게 상하좌우 “방향키” 예약할 때 함께 진행하게 된다.
🔥 DP + BFS 사용한 풀이 ⭕
int solution(vector<vector<int>> board, int r, int c) {
int answer = INF;
vector<vector<Pos>> pos(7); // 카드 번호(인덱스) 별로 위치 저장. pos[카드넘버][0], pos[카드넘버][1]
for (int i = 0; i < 4; ++i)
for (int j = 0; j < 4; ++j)
if (board[i][j] != 0)
pos[board[i][j]].push_back({ i, j });
vector<int> card_num; // 현재 화면에 존재하는 카드 종류(넘버)들이 저장된다.
for (int i = 1; i <= 6; ++i) // ex) [2, 4, 5]
if (!pos[i].empty())
card_num.push_back(i);
int n = card_num.size();
/* next_permutation 으로 현재 화면에 존재하는 카드 종류들의 모든 순서를 하나 하나씩 결정하고 해당 순열의 "최소 조작 횟수"를 DP 로 구하여 테이블에 저장한다. */
do {
// 전체적인 선택 순서를 하나 정해놓고 조작 횟수를 구할거라 매 순서마다 원래의 화면에서 카드를 제거하기 위해 board 복사한 board_temp 만듬. 여기의 카드를 제거할 것이다.
vector<vector<int>> board_temp = board;
// dp[i][0] : 화면 내의 카드들 중 i 번째 카드의 <첫 번째 카드 👉 두 번째 카드> 순서로 선택할 때의 최소 조작 횟수
// dp[i][1] : 화면 내의 카드들 중 i 번째 카드의 <두 번째 카드 👉 첫 번째 카드> 순서로 선택할 때의 최소 조작 횟수
vector<vector<int>> dp(n, vector<int>(2));
// i = 0 일 때 처리 (i = 0 번째 카드)
// 두 가지 선택 순서에 따른 "최소 조작 횟수" 저장
// 점화식 설명은 밑에 설명
dp[0][0] = bfs(board_temp, { r, c }, pos[card_num[0]][0])
+ bfs(board_temp, pos[card_num[0]][0], pos[card_num[0]][1])
+ 2;
dp[0][1] = bfs(board_temp, { r, c }, pos[card_num[0]][1])
+ bfs(board_temp, pos[card_num[0]][1], pos[card_num[0]][0])
+ 2;
// 선택한 두 카드 제거
board_temp[pos[card_num[0]][0].row][pos[card_num[0]][0].col] = 0;
board_temp[pos[card_num[0]][1].row][pos[card_num[0]][1].col] = 0;
for (int i = 1; i < n; ++i) {
// 나머지 카드들
// 두 가지 선택 순서에 따른 "최소 조작 횟수" 저장
// 점화식 설명은 밑에 설명
dp[i][0] = min(dp[i - 1][0] + bfs(board_temp, pos[card_num[i - 1]][1], pos[card_num[i]][0]),
dp[i - 1][1] + bfs(board_temp, pos[card_num[i - 1]][0], pos[card_num[i]][0]))
+ bfs(board_temp, pos[card_num[i]][0], pos[card_num[i]][1])
+ 2;
dp[i][1] = min(dp[i - 1][0] + bfs(board_temp, pos[card_num[i - 1]][1], pos[card_num[i]][1]),
dp[i - 1][1] + bfs(board_temp, pos[card_num[i - 1]][0], pos[card_num[i]][1]))
+ bfs(board_temp, pos[card_num[i]][1], pos[card_num[i]][0])
+ 2;
// 선택한 두 카드 제거
board_temp[pos[card_num[i]][0].row][pos[card_num[i]][0].col] = 0;
board_temp[pos[card_num[i]][1].row][pos[card_num[i]][1].col] = 0;
}
int res = min(dp[n - 1][0], dp[n - 1][1]);
answer = min (res, answer);
} while (next_permutation(card_num.begin(), card_num.end()));
return answer;
}
확실히 DP 가 빠르네..
풀이는 위 유튜브 영상을 참고하였다. bfs 함수와 Pos 구조체, 전역 변수들은 두 번째 풀이를 그대로 사용하였으니 이에 대한 코드와 해설은 생략했다.
next_permutation으로 현재 화면 내에 있는 카드들의 선택 순서를 결정하고 매번 순서마다 DP를 통하여 해당 순서의 최소 조작횟수를 구한다. 해당 순서의 최종적인 “최소 조작 횟수”는 dp[n - 1][0] 와 dp[n - 1][1] 둘 중 더 작은 값으로 고르면 된다. 그리고 answer와 비교하면 된다. answer에는 현재까지 본 모든 순서에서의 최소 조작 횟수를 저장한다.
- 현재 순서에서 0 번째로 선택한 카드(제일 처음 선택된 카드)의 점화식
dp[0][0]: 0 번째로 선택한 카드의 첫 번째 카드 L를 먼저 선택한 후 두 번째 카드를 선택했을 때의 최소 조작 횟수. (L -> R)+(출발지 👉 0 번째로 선택한 카드의 첫 번째 카드) 에 필요한 조작횟수- bfs(board_temp, { r, c }, pos[card_num[0]][0])
+(0 번째로 선택한 카드의 첫 번째 카드 👉0 번째로 선택한 카드의 두 번째 카드) 에 필요한 조작횟수- bfs(board_temp, pos[card_num[0]][0], pos[card_num[0]][1])
+2 (두 카드를 Enter 누르는데 필요한)
dp[0][1]: 0 번째로 선택한 카드의 두 번째 카드 R를 먼저 선택한 후 첫 번째 카드를 선택했을 때의 최소 조작 횟수. (R -> L)+(출발지 👉 0 번째로 선택한 카드의 두 번째 카드) 에 필요한 조작횟수- bfs(board_temp, { r, c }, pos[card_num[0]][1])
+(0 번째로 선택한 카드의 두 번째 카드 👉0 번째로 선택한 카드의 첫 번째 카드) 에 필요한 조작횟수- bfs(board_temp, pos[card_num[0]][1], pos[card_num[0]][0])
+2 (두 카드를 Enter 누르는데 필요한)
- i 번째로 선택한 카드들의 점화식
dp[i][0]: i 번째로 선택한 카드의 첫 번째 카드 L를 먼저 선택한 후 두 번째 카드를 선택했을 때의 최소 조작 횟수. (L -> R)- L (i-1) -> L (i) 과 R (i - 1) -> L (i) 둘 중 더 작은 조작 횟수
+L -> R 조작횟수+2+i - 1 번째 카드의 두 번째 카드에서 왔을 때와 i - 1 번째 카드의 첫 번째 카드에서 왔을 때, 이렇게 둘 중 더 작은 조작 횟수를 가지는 것을 선택한다.- min
- i - 1 번째로 선택한 카드의 (첫번째 👉 두번째) 카드 까지의 조작 횟수
+(i - 1 번째로 선택한 카드의 두 번째 카드 👉 i 번째로 선택한 카드의 첫 번째 카드) 에 필요한 조작 횟수- i - 1 번째 카드의 두 번째 카드(첫번째->두번째 dp[i-1][0])에서 i 번째의 첫번째 카드로 왔을 때
- dp[i - 1][0] + bfs(board_temp, pos[card_num[i - 1]][1], pos[card_num[i]][0])
- i - 1 번째로 선택한 카드의 (두번째 👉 첫번째) 카드 까지의 조작 횟수
+(i - 1 번째로 선택한 카드의 첫 번째 카드 👉 i 번째로 선택한 카드의 첫 번째 카드) 에 필요한 조작 횟수- i - 1 번째 카드의 첫 번째 카드(두번째->첫번째 dp[i-1][1])에서 i 번째의 첫번째 카드로 왔을 때
- dp[i - 1][1] + bfs(board_temp, pos[card_num[i - 1]][0], pos[card_num[i]][0])
- i - 1 번째로 선택한 카드의 (첫번째 👉 두번째) 카드 까지의 조작 횟수
- min
+i 번째 카드의 (첫 번째 카드 👉 두 번째 카드) 에 필요한 조작횟수 (L -> R)- bfs(board_temp, pos[card_num[i]][0], pos[card_num[i]][1])
+2 (두 카드를 Enter 누르는데 필요한)
- L (i-1) -> L (i) 과 R (i - 1) -> L (i) 둘 중 더 작은 조작 횟수
dp[i][1]: i 번째로 선택한 카드의 두 번째 카드 R를 먼저 선택한 후 첫 번째 카드를 선택했을 때의 최소 조작 횟수. (R -> L)- L (i-1) -> R (i) 과 R (i - 1) -> R (i) 둘 중 더 작은 조작 횟수
+R -> L 조작횟수+2+i - 1 번째 카드의 두 번째 카드에서 왔을 때와 i - 1 번째 카드의 첫 번째 카드에서 왔을 때, 이렇게 둘 중 더 작은 조작 횟수를 가지는 것을 선택한다.- min
- i - 1 번째로 선택한 카드의 (첫번째 👉 두번째) 카드 까지의 조작 횟수
+(i - 1 번째로 선택한 카드의 두 번째 카드 👉 i 번째로 선택한 카드의 두 번째 카드) 에 필요한 조작 횟수- i - 1 번째 카드의 두 번째 카드(첫번째->두번째 dp[i-1][0])에서 i 번째의 두번째 카드로 왔을 때
- dp[i - 1][0] + bfs(board_temp, pos[card_num[i - 1]][1], pos[card_num[i]][1])
- i - 1 번째로 선택한 카드의 (두번째 👉 첫번째) 카드 까지의 조작 횟수
+(i - 1 번째로 선택한 카드의 첫 번째 카드 👉 i 번째로 선택한 카드의 두 번째 카드) 에 필요한 조작 횟수- i - 1 번째 카드의 첫 번째 카드(두번째->첫번째 dp[i-1][1])에서 i 번째의 두번째 카드로 왔을 때
- dp[i - 1][1] + bfs(board_temp, pos[card_num[i - 1]][0], pos[card_num[i]][1])
- i - 1 번째로 선택한 카드의 (첫번째 👉 두번째) 카드 까지의 조작 횟수
- min
+i 번째 카드의 (두 번째 카드 👉 첫 번째 카드) 에 필요한 조작횟수 (R -> l)- bfs(board_temp, pos[card_num[i]][1], pos[card_num[i]][0])
+2 (두 카드를 Enter 누르는데 필요한)
- L (i-1) -> R (i) 과 R (i - 1) -> R (i) 둘 중 더 작은 조작 횟수
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글 남기기