문제 설명
문제 설명
게임 개발자인 베로니는 개발 연습을 위해 다음과 같은 간단한 카드 짝맞추기 보드 게임을 개발해 보려고 합니다.
게임이 시작되면 화면에는 카드 16장이 뒷면을 위로하여 4 x 4 크기의 격자 형태로 표시되어 있습니다. 각 카드의 앞면에는 카카오프렌즈 캐릭터 그림이 그려져 있으며, 8가지의 캐릭터 그림이 그려진 카드가 각기 2장씩 화면에 무작위로 배치되어 있습니다.
유저가 카드를 2장 선택하여 앞면으로 뒤집었을 때 같은 그림이 그려진 카드면 해당 카드는 게임 화면에서 사라지며, 같은 그림이 아니라면 원래 상태로 뒷면이 보이도록 뒤집힙니다. 이와 같은 방법으로 모든 카드를 화면에서 사라지게 하면 게임이 종료됩니다.
게임에서 카드를 선택하는 방법은 다음과 같습니다.
- 카드는 커서를 이용해서 선택할 수 있습니다.
- 커서는 4 x 4 화면에서 유저가 선택한 현재 위치를 표시하는 굵고 빨간 테두리 상자를 의미합니다.
- 커서는 [Ctrl] 키와 방향키에 의해 이동되며 키 조작법은 다음과 같습니다.
- 방향키 ←, ↑, ↓, → 중 하나를 누르면, 커서가 누른 키 방향으로 1칸 이동합니다.
- [Ctrl] 키를 누른 상태에서 방향키 ←, ↑, ↓, → 중 하나를 누르면, 누른 키 방향에 있는 가장 가까운 카드로 한번에 이동합니다.
- 만약, 해당 방향에 카드가 하나도 없다면 그 방향의 가장 마지막 칸으로 이동합니다.
- 만약, 누른 키 방향으로 이동 가능한 카드 또는 빈 공간이 없어 이동할 수 없다면 커서는 움직이지 않습니다.
- 커서가 위치한 카드를 뒤집기 위해서는 [Enter] 키를 입력합니다.
- [Enter] 키를 입력해서 카드를 뒤집었을 때
- 앞면이 보이는 카드가 1장 뿐이라면 그림을 맞출 수 없으므로 두번째 카드를 뒤집을 때 까지 앞면을 유지합니다.
- 앞면이 보이는 카드가 2장이 된 경우, 두개의 카드에 그려진 그림이 같으면 해당 카드들이 화면에서 사라지며, 그림이 다르다면 두 카드 모두 뒷면이 보이도록 다시 뒤집힙니다.
- [Enter] 키를 입력해서 카드를 뒤집었을 때
베로니는 게임 진행 중 카드의 짝을 맞춰 몇 장 제거된 상태에서 카드 앞면의 그림을 알고 있다면, 남은 카드를 모두 제거하는데 필요한 키 조작 횟수의 최솟값을 구해 보려고 합니다. 키 조작 횟수는 방향키와 [Enter] 키를 누르는 동작을 각각 조작 횟수 1로 계산하며, [Ctrl] 키와 방향키를 함께 누르는 동작 또한 조작 횟수 1로 계산합니다.
다음은 카드가 몇 장 제거된 상태의 게임 화면에서 커서를 이동하는 예시입니다.
아래 그림에서 빈 칸은 이미 카드가 제거되어 없어진 칸을 의미하며, 그림이 그려진 칸은 카드 앞 면에 그려진 그림을 나타냅니다.
예시에서 커서는 두번째 행, 첫번째 열 위치에서 시작하였습니다.
[Enter] 입력, ↓ 이동, [Ctrl]+→ 이동, [Enter] 입력 = 키 조작 4회
[Ctrl]+↑ 이동, [Enter] 입력, [Ctrl]+← 이동, [Ctrl]+↓ 이동, [Enter] 입력 = 키 조작 5회
[Ctrl]+→ 이동, [Enter] 입력, [Ctrl]+↑ 이동, [Ctrl]+← 이동, [Enter] 입력 = 키 조작 5회
위와 같은 방법으로 커서를 이동하여 카드를 선택하고 그림을 맞추어 카드를 모두 제거하기 위해서는 총 14번(방향 이동 8번, [Enter] 키 입력 6번)의 키 조작 횟수가 필요합니다.
[문제]
현재 카드가 놓인 상태를 나타내는 2차원 배열 board와 커서의 처음 위치 r, c가 매개변수로 주어질 때, 모든 카드를 제거하기 위한 키 조작 횟수의 최솟값을 return 하도록 solution 함수를 완성해 주세요.
[제한사항]
- board는 4 x 4 크기의 2차원 배열입니다.
- board 배열의 각 원소는 0 이상 6 이하인 자연수입니다.
- 0은 카드가 제거된 빈 칸을 나타냅니다.
- 1 부터 6까지의 자연수는 2개씩 들어있으며 같은 숫자는 같은 그림의 카드를 의미합니다.
- 뒤집을 카드가 없는 경우(board의 모든 원소가 0인 경우)는 입력으로 주어지지 않습니다.
- r은 커서의 최초 세로(행) 위치를 의미합니다.
- c는 커서의 최초 가로(열) 위치를 의미합니다.
- r과 c는 0 이상 3 이하인 정수입니다.
- 게임 화면의 좌측 상단이 (0, 0), 우측 하단이 (3, 3) 입니다.
[입출력 예]
boardrcresult
| [[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]] | 1 | 0 | 14 |
| [[3,0,0,2],[0,0,1,0],[0,1,0,0],[2,0,0,3]] | 0 | 1 | 16 |
접근 방법
삼성 유형과 비슷한 문제였는데 상당히 복잡하게 느껴졌습니다.
일단 문제의 큰 틀을 잡아보면 4가지 과정으로 나눌 수 있습니다.
1. 어떤 짝 먼저 맞춰갈지에 대한 순서 정하기
2. 순서를 정했다면 한 쌍에서 어떤 카드부터 선택 할지 정하기
3. 2번 과정까지 완료 됬다면 각각 지점사이에 이동 횟수를 알아내어 전체 경로의 이동횟수를 구하기
4. 3번 과정을 반복하며 최소값 갱신
1. 어떤 짝 먼저 맞춰갈지에 대한 순서 정하기
만약 짝이 1,2,3이 있다면 1->2->3 순서로 해결할지 1->3->2의 순서로 해결할지
3->1->2 등등의 순서를 정해주어야 합니다. 즉 모든 가능한 순열을 구해야 합니다.
void combinations(vector<bool> &visited, vector<vector<int>> &combs, vector<int> comb, vector<int> &card){
if(comb.size() == card.size()){
combs.push_back(comb);
return;
}
for(int i=0;i<card.size();i++){
if(!visited[i]){
visited[i] = true;
comb.push_back(card[i]);
combinations(visited, combs, comb, card);
comb.pop_back();
visited[i] = false;
}
}
}combs = 순열들의 집합, comb = 한 순열, visited = 방문여부, card = 짝(ex, {1,2,3})
순열은 백트래킹 기법을 사용하여 구할 수 있습니다.
이 때 card는 아래와 같은 방법으로 구할 수 있습니다. 또한 카드의 좌표정보를 갖고있는 info를 갱신하여 줍니다. info[카드번호] = {{x1,y1}, {x2, y2}}
//map == board
vector<int> findcard(){
vector<bool> check_card(7, false);
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(map[i][j]!=0){
check_card[map[i][j]] = true;
info[map[i][j]].push_back({i, j});
}
vector<int> card;
for(int i=0;i<check_card.size();i++)
if(check_card[i])
card.push_back(i);
return card;
}
2. 순서를 정했다면 한 쌍에서 어떤 카드부터 선택 할지 정하기
각각의 짝은 2장의 카드로 이루어져 있습니다. 만약 [a->b->c->d]라는 순서를 결정지었을 때
a라는 짝이 a1, a2 두 장의 카드로 이루어져 있다면 a1을 먼저 방문하고 a2를 방문할지, a2를 먼저 방문하고 a1을 방문할지 결정하고 b, c, d에 대해서도 각각의 카드의 방문 순서를 지정해주어야 합니다.
ex 1) a1 -> a2 -> b1 -> b2 -> c2 -> c1 -> d2 -> d1
ex 2) a2 -> a1 -> b1 -> b2 -> c1 -> c2 -> d2 -> d1
void decide_path(vector<vector<pair<int, int>>> &paths, vector<pair<int, int>> path, vector<int> &comb, int idx){
if(idx == comb.size()){
paths.push_back(path);
return;
}
int num = comb[idx];
path.push_back(info[num][0]);
path.push_back(info[num][1]);
decide_path(paths, path, comb, idx+1);
path.pop_back();
path.pop_back();
path.push_back(info[num][1]);
path.push_back(info[num][0]);
decide_path(paths, path, comb, idx+1);
path.pop_back();
path.pop_back();
}paths = path들의 집합, path = 이동할 좌표의 순열, comb = 한 순열
이동할 좌표의 순열 또한 백트래킹을 사용하여 구할 수 있습니다.
3. 2번 과정까지 완료가 되었다면 각각 지점사이에 이동 횟수를 알아내어 전체 경로의 이동횟수를 구해야 합니다.
한 좌표에서 다른 좌표로 이동할 수 있는 경우는 총 8가지가 있습니다. 상하좌우 한 칸씩 이동하는 방법 4개, ctrl키를 누른뒤 상하좌우로 이동하는 방법이 4개 있습니다. 이 때 저는 BFS를 통해 해결을 하였습니다.
int BFS(pair<int, int> start, pair<int, int> end){
queue<pair<pair<int, int>, int>> q; //좌표와 레벨
vector<vector<bool>> visited(4, vector<bool>(4,false));
q.push({start, 0});
visited[start.first][start.second] = true;
while(!q.empty()){
int x = q.front().first.first;
int y = q.front().first.second;
int level = q.front().second;
q.pop();
for(int i=0;i<8;i++){ //8가지 방향에 대해
pair<int, int> next_xy = findNext(i,x,y); //다음 좌표!!!
int next_x = next_xy.first;
int next_y = next_xy.second;
if(inRange(next_x, next_y) && !visited[next_x][next_y]){
visited[next_x][next_y] = true;
if(next_x == end.first && next_y == end.second)
return level + 1;
q.push({{next_x, next_y}, level+1});
}
}
}
return 0;
}위와 같이 BFS를 사용하여 start(출발 좌표)와 end(도착 좌표)까지의 최소 이동횟수를 구할 수 있는데 findNext()함수를 통해 다음 좌표를 구할 수 있습니다.
findNext(int dir, int x, int y)
pair<int, int> findNext(int dir, int x, int y){
vector<pair<int, int>> nextdir = {{1,0},{0,1},{-1,0},{0,-1}};
//처음 4방향은 1칸만 이동
if(dir < 4)
return { x + nextdir[dir].first, y + nextdir[dir].second};
else{ //나머지 4방향은 끝 또는 카드가 있는 곳까지 이동(ctrl + 방향키)
dir -= 4;
while(inRange(x + nextdir[dir].first, y + nextdir[dir].second)){
x += nextdir[dir].first;
y += nextdir[dir].second;
if(tmp[x][y] != 0)
break;
}
return {x, y};
}
}
4. 3번 과정을 반복하며 최소값 갱신
int processOneComb(vector<int> &comb, int r, int c){
vector<vector<pair<int, int>>> paths;
vector<pair<int, int>> path;
decide_path(paths, path, comb, 0);
int mindist = 0xFFFFFFF;
for(int i=0;i<paths.size();i++){
tmp = map; //한 순열에 대한 board상태 초기화
int dist = 0;
for(int j=0;j<paths[i].size();j++){ //한 경로 조합에 대한 거리
//각각 dist에 +1하는 이유는 엔터동작 때문임
if(j==0) dist += BFS({r,c}, paths[i][j]) + 1;
else dist += BFS(paths[i][j - 1], paths[i][j]) + 1;
tmp[paths[i][j].first][paths[i][j].second] = 0; //이동한 좌표의 카드 삭제
}
mindist = min(mindist, dist);
}
return mindist;
}
소스 코드
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
vector<pair<int,int>> info[7];
vector<vector<int>> map;
vector<vector<int>> tmp;
bool inRange(int x, int y){
return (0 <= x && x < 4 && 0 <= y && y < 4);
}
void combinations(vector<bool> &visited, vector<vector<int>> &combs, vector<int> comb, vector<int> &card){
if(comb.size() == card.size()){
combs.push_back(comb);
return;
}
for(int i=0;i<card.size();i++){
if(!visited[i]){
visited[i] = true;
comb.push_back(card[i]);
combinations(visited, combs, comb, card);
comb.pop_back();
visited[i] = false;
}
}
}
vector<vector<int>> find_combs(vector<int> &card){
vector<bool> visited(card.size(), false);
vector<vector<int>> combs;
vector<int> comb;
combinations(visited, combs, comb, card);
return combs;
}
vector<int> findcard(){
vector<bool> check_card(7, false);
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(map[i][j]!=0){
check_card[map[i][j]] = true;
info[map[i][j]].push_back({i, j});
}
vector<int> card;
for(int i=0;i<check_card.size();i++)
if(check_card[i])
card.push_back(i);
return card;
}
void decide_path(vector<vector<pair<int, int>>> &paths, vector<pair<int, int>> path, vector<int> &comb, int idx){
if(idx == comb.size()){
paths.push_back(path);
return;
}
int num = comb[idx];
path.push_back(info[num][0]);
path.push_back(info[num][1]);
decide_path(paths, path, comb, idx+1);
path.pop_back();
path.pop_back();
path.push_back(info[num][1]);
path.push_back(info[num][0]);
decide_path(paths, path, comb, idx+1);
path.pop_back();
path.pop_back();
}
pair<int, int> findNext(int dir, int x, int y){
vector<pair<int, int>> nextdir = {{1,0},{0,1},{-1,0},{0,-1}};
if(dir < 4)
return { x + nextdir[dir].first, y + nextdir[dir].second};
else{
dir -= 4;
while(inRange(x + nextdir[dir].first, y + nextdir[dir].second)){
x += nextdir[dir].first;
y += nextdir[dir].second;
if(tmp[x][y] != 0)
break;
}
return {x, y};
}
}
int BFS(pair<int, int> start, pair<int, int> end){
queue<pair<pair<int, int>, int>> q; //좌표와 레벨
vector<vector<bool>> visited(4, vector<bool>(4,false));
q.push({start, 0});
visited[start.first][start.second] = true;
while(!q.empty()){
int x = q.front().first.first;
int y = q.front().first.second;
int level = q.front().second;
q.pop();
for(int i=0;i<8;i++){
pair<int, int> next_xy = findNext(i,x,y);
int next_x = next_xy.first;
int next_y = next_xy.second;
if(inRange(next_x, next_y) && !visited[next_x][next_y]){
visited[next_x][next_y] = true;
if(next_x == end.first && next_y == end.second)
return level + 1;
q.push({{next_x, next_y}, level+1});
}
}
}
return 0;
}
int processOneComb(vector<int> &comb, int r, int c){
vector<vector<pair<int, int>>> paths;
vector<pair<int, int>> path;
decide_path(paths, path, comb, 0);
int mindist = 0xFFFFFFF;
for(int i=0;i<paths.size();i++){
tmp = map; //한 순열에 대한 board상태 초기화
int dist = 0;
for(int j=0;j<paths[i].size();j++){ //한 경로 조합에 대한 거리
//각각 dist에 +1하는 이유는 엔터동작 때문임
if(j==0) dist += BFS({r,c}, paths[i][j]) + 1;
else dist += BFS(paths[i][j - 1], paths[i][j]) + 1;
tmp[paths[i][j].first][paths[i][j].second] = 0; //이동한 좌표의 카드 삭제
}
mindist = min(mindist, dist);
}
return mindist;
}
int solution(vector<vector<int>> board, int r, int c) {
int answer = 0xFFFFFFF;
map = board;
vector<int> card = findcard();
vector<vector<int>> combs = find_combs(card);
for(int i=0;i<combs.size();i++){
answer = min(answer, processOneComb(combs[i], r, c));
}
return answer;
}'알고리즘 > 프로그래머스' 카테고리의 다른 글
| [C++, Java] 2021 카카오 블라인드 매출 하락 최소화 (0) | 2021.02.10 |
|---|---|
| [C++] 2021 카카오 블라인드 순위 검색 (0) | 2021.02.08 |
| [C++] 2021 카카오 블라인드 광고 삽입 (5) | 2021.02.08 |
| [C++] 2020 카카오 블라인드 기둥과 보 설치 (2) | 2021.02.03 |
| [C++] 2020 카카오 블라인드 가사 검색 (1) | 2021.02.03 |
