코딩테스트 -- 부대복귀 - (프로그래머스 / C++)

프로그래머스

 

문제!

---

강철부대의 각 부대원이 여러 지역에 뿔뿔이 흩어져 특수 임무를 수행 중입니다. 지도에서 강철부대가 위치한 지역을 포함한 각 지역은 유일한 번호로 구분되며, 두 지역 간의 길을 통과하는 데 걸리는 시간은 모두 1로 동일합니다. 임무를 수행한 각 부대원은 지도 정보를 이용하여 최단시간에 부대로 복귀하고자 합니다. 다만 적군의 방해로 인해, 임무의 시작 때와 다르게 되돌아오는 경로가 없어져 복귀가 불가능한 부대원도 있을 수 있습니다.

강철부대가 위치한 지역을 포함한 총지역의 수 n, 두 지역을 왕복할 수 있는 길 정보를 담은 2차원 정수 배열 roads, 각 부대원이 위치한 서로 다른 지역들을 나타내는 정수 배열 sources, 강철부대의 지역 destination이 주어졌을 때, 주어진 sources의 원소 순서대로 강철부대로 복귀할 수 있는 최단시간을 담은 배열을 return하는 solution 함수를 완성해주세요. 복귀가 불가능한 경우 해당 부대원의 최단시간은 -1입니다.

 

---

각각의 부대원을 목적지에 복귀시킬때 최소시간들을 구해주는 문제입니다. 

 

간단한 문제라고 생각하고 바로 dfs 완전탐색을 돌리게되면!

 

아래처럼 짤 수있습니다.

#include <string>
#include <vector>
#include <iostream>
using namespace std;



vector<int>cost;//비용

void find(vector<vector<int>> &map, vector<int> visit, int n){
    //n지점에서 갈수있는곳으로의 완탐   
    for(int i=1;i<=cost.size();i++){//연결되어있는지 확인
        
        if(map[n][i]==1 and visit[i]==0){
            
            
            if(cost[i]==-1){
                cost[i]=cost[n]+1;
            }
            else{
                cost[i]=min(cost[i],cost[n]+1);
            }
            
            if(cost[n]>=cost[i]){
                continue;
            }
            
            visit[i]=1;
            find(map,visit,i);
            visit[i]=0;
        }
    }
    
    return;
}


vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer;
    
    vector<vector<int>>map(n+1,vector<int>(n+1,0));
    
    vector<int>visit(n+1,0); //방문
    for(int i=0;i<=n;i++){
        cost.push_back(-1);
    }
    
    for(int i=0;i<roads.size();i++){//맵구성
        map[roads[i][0]][roads[i][1]]=1;
        map[roads[i][1]][roads[i][0]]=1;
    }

    //목적지가 정해져있다
    
    //완탐  --- 탐색알고리즘
    
    cost[destination]=0;
    find(map,visit,destination);
    
    
    
    for(int i=0;i<sources.size();i++){
        answer.push_back(cost[sources[i]]);
    }
    return answer;
}

하지만 이렇게 짜게되면 6번부터 시간초과 나네요..

답은 나오지만 최적의 답이 아닌코드!

 

 

 문제에서 얻을수 있는 힌트를 정리해보면

1. 목적지가 하나다

2. 복귀못할수도 있다.

3. 길을 통과하는 시간은 1이다.

 

길을 통과하는 시간이 일정하다는 부분에서

다익스트라, 와샬 알고리즘은 사용하지 않아도 된다는 점을 알수있어서

 

이번엔 bfs로 풀어보았습니다.

 

 

.....dfs보다는 빨라졌지만 그래도 시간초과가 나네요....

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

queue<int>save;
vector<int>cost;//비용

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer;
    
    vector<vector<int>>map(n+1,vector<int>(n+1,0)); // 맵구성
    vector<int>visit(n+1,0); //방문
    
    for(int i=0;i<=n;i++){
        cost.push_back(-1);
    }
    
    for(int i=0;i<roads.size();i++){//맵구성
        map[roads[i][0]][roads[i][1]]=1;
        map[roads[i][1]][roads[i][0]]=1;
    }

    //목적지가 정해져있다
    
    //완탐  --- 탐색알고리즘
    
    cost[destination]=0;
    save.push(destination);
    visit[destination]=1;
    
    while(save.size()){
        int memo=save.front();
        save.pop();
        for(int i=1;i<n+1;i++){
            if(map[memo][i]==1 and visit[i]==0){
                cost[i]=cost[memo]+1;
                save.push(i);
                visit[i]=1;
            }
        }
    }
    
    for(int i=0;i<sources.size();i++){
        answer.push_back(cost[sources[i]]);
    }
    return answer;
}

 

방법은 bfs가 맞는것 같습니다...

여기까지 하니 맵구성에서 문제가 있음을 깨달았습니다!

 

위의 코드들은 map[출발][도착] = 길있음 =1  이런식으로 저장이 되어있는데

 

이게 길의 길이가 1로 고정되어있기에  map[출발지]={도착지들~~}  

즉 1차원 배열로 충분히 가능한 문제였습니다.. 전 늦게 알아차렸네요

 

그럼 시작!

---

위의 코드들과 풀이 방법은 같습니다

 

일단 벡터들과 큐를 선언해줍시다.

vector<vector<int>>map(n+1); // 맵구성
    vector<int>visit(n+1,0); //방문
    vector<int>cost;//비용
    queue<int>save;

 

코스트는 -1로 모두 초기화 해주고

for(int i=0;i<=n;i++){
        cost.push_back(-1);
    }

맵 구성을 아래와 같이 바꾸어 줍시다!!

for(int i=0;i<roads.size();i++){//맵구성
        map[roads[i][0]].push_back(roads[i][1]);
        map[roads[i][1]].push_back(roads[i][0]);
    }

 

도착점을 아래처럼 처리해주고

cost[destination]=0;
    save.push(destination);/// queue
    visit[destination]=1;

 

그 다음 큐를 이용해 bfs탐색을 해주시면 끝!

while(save.size()){
        memo=save.front();
        save.pop();
        for(int i=0;i<map[memo].size();i++){// map[memo]에 들어있는것만 탐색
            index=map[memo][i];
            if(visit[index]==0){
                cost[index]=cost[memo]+1;
                save.push(index);
                visit[index]=1;
            }
        }
    }

 

 

*ALL

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;



vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer; 
    
    vector<vector<int>>map(n+1); // 맵구성
    vector<int>visit(n+1,0); //방문
    vector<int>cost;//비용
    queue<int>save;
    
    for(int i=0;i<=n;i++){
        cost.push_back(-1);
    }
    
    for(int i=0;i<roads.size();i++){//맵구성
        map[roads[i][0]].push_back(roads[i][1]);
        map[roads[i][1]].push_back(roads[i][0]);
    }

    //목적지가 정해져있다
    
    //완탐  --- 탐색알고리즘
    
    cost[destination]=0;
    save.push(destination);/// queue
    visit[destination]=1;
    
    int index=0;
    int memo =0;
    
    while(save.size()){
        memo=save.front();
        save.pop();
        for(int i=0;i<map[memo].size();i++){// map[memo]에 들어있는것만 탐색
            index=map[memo][i];
            if(visit[index]==0){
                cost[index]=cost[memo]+1;
                save.push(index);
                visit[index]=1;
            }
        }
    }
    
    for(int i=0;i<sources.size();i++){
        answer.push_back(cost[sources[i]]);
    }
    return answer;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!