[코드트리] 동전 챙기기 ( C++)

[문제]

https://www.codetree.ai/problems/collect-coins/description

코드트리

[풀이]

 

삼성전자 공채 모의 코딩테스트가 코드트리에 있길래 한번 풀어봤다. 굉장히 삼성스러운 문제..

 

NXN 격자에는  동전과  벽이 존재하며 주어진 시작점과 끝점 까지의 최단 거리를 구하면 된다.

시작점에서 끝점으로 가기 위해서는 최소 3개의 동전을 획득해야 하며 획득하는 동전의 순서는 동전의 번호가 작은 것부터 오름차순으로 획득할 수 있다.

또한 동전이 있는 곳을 지나가도 동전을 가져가지 않을 수 있으며 지나간 위치를 다시 지나갈 수 있다.

BFS와  DFS를 사용해 문제를 해결했다.

 

먼저 주어진 동전의 정보를 coin 이라는 벡터에 저장해두었다. 그리고 coin 벡터를 동전 번호를 기준으로 오름차순 정렬을 해주었다.

그리고 DFS를 통해 coin 벡터에 담긴 순서대로 동전을 선택하여 selectedCoin 벡터에 coin 벡터에서의 해당  동전의 index를 push했다.

DFS를 사용해 동전의 숫자가 오름차순으로 3개의 동전을 선택하여 최단거리를 구하였다.

최단거리를 구하는 방법으로는 BFS를 사용해 시작지점부터 종점부분까지의 거리를 구했다.

BFS는 최초 방문이 최단 경로가 되므로 queue에서 pop한 좌표가 종점인 경우 break 하도록 추가해줬다. (이거 안해주면 시간초과 발생)

최단거리 =  시작점부터 첫번째 동전까지의 거리 + 첫번째 동전 to 두번째 동전 거리 + 두번째 동전 to 세번째 동전 거리 + 세번째 동전 to 종점까지의 거리 

 

이 때 각 거리 계산 중 이동할 수 없는 좌표가 발생한다면 해당경로는 불가능한 경로이므로 -1을 return 하여 이동 불가능한 경로로 처리하였다.

 

[코드]

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

#define MAX 20

using namespace std;

struct pos{
    int x,y;
};

struct coinInfo{
    int idx,x,y;
};

int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

int res=MAX*MAX;
int map[MAX][MAX]={0,};
int N;

pos startPos,endPos;

vector<coinInfo> coin;
vector<int> selected;

bool comp(coinInfo a, coinInfo b)
{
    if ( a.idx < b.idx) return true;
    return false;
}

int BFS(pos from, pos to)
{
    int visited[MAX][MAX]={0,};
    queue<pos> q;
    q.push(from);
    visited[from.x][from.y]=1;
    while(!q.empty()){
        int x= q.front().x;
        int y= q.front().y;
        q.pop();
        if(x==to.x && y == to.y)    break;
        for(int d=0;d<4;d++){
            int nx = x+dx[d];
            int ny = y+dy[d];
            
            if(nx<0||ny<0||nx>=N||ny>=N||map[nx][ny]==-1||visited[nx][ny] != 0)   continue;
            visited[nx][ny] = visited[x][y] + 1;
            q.push({nx,ny});
        }
    }
    
    return visited[to.x][to.y]-1;
}

int isPossible()
{
    int totalLen =0;
    int fromX,fromY;
    int toX, toY;
    
    for(int i=0;i<4;i++){
        if(i == 0){
            fromX = startPos.x; fromY = startPos.y;
            toX = coin[selected[i]].x;  toY = coin[selected[i]].y;
        } else if( i == 3){
            fromX = coin[selected[2]].x;    fromY = coin[selected[2]].y;
            toX = endPos.x;  toY = endPos.y;
        } else {
            fromX = coin[selected[i-1]].x;    fromY = coin[selected[i-1]].y;
            toX = coin[selected[i]].x;  toY = coin[selected[i]].y;
        }
        int len = BFS({fromX,fromY},{toX,toY});
        if( len == -1){
            totalLen = -1;
            break;
        }   else    totalLen += len;
    }
    
    return totalLen;
}

void selectCoin(int cnt, int idx)
{
    if( cnt == 3){
        int len = isPossible();
        if( len == -1)  return;
        if( len < res)  res = len;
        return ;
    }
    for(int i=idx;i<coin.size();i++){
        selected.push_back(i);
        selectCoin(cnt+1, i+1);
        selected.pop_back();
    }
}

void input()
{
    cin >> N;
    for(int i=0;i<N;i++){
        string str;
        cin >> str;
        for(int j=0;j<N;j++){
            
            if(str[j] == '#')   map[i][j]=-1;
            else if(str[j] == '.')  map[i][j]=0;
            else if(str[j] == 'S')  startPos={i,j};
            else if(str[j] == 'E')  endPos={i,j};
            else{
                map[i][j] = str[j] - '0';
                coin.push_back({map[i][j] , i, j});
            }
        }
    }
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    input();
    // 코인 오름차순 정렬
    sort(coin.begin(), coin.end(), comp);
    selectCoin(0,0);
    if(res == MAX*MAX)    cout << "-1";
    else    cout << res;
    
    return 0;
}