[프로그래머스 C++] 부대복귀 (추가!)

< 해설 >

(코드 추가)

문제를 다 풀고 다른 공부하다가 문득 들은 생각인데 어짜피 모든 경로는 정해져 있다. 그리고 도착해야하는 목적지가 모두가 같으므로 도착지에서 각 노드별로 bfs를 모두 돌며 얼마나 떨어져있는지 count 를 전부 계산한다. 그리고 sources에 있는 인덱스별 답만 추출하면 되는 문제였다... 

 

수정해서 돌려보니까 정말정말정말 빨라졌다... 왜 처음엔 이 생각을 못했을까..ㅋㅋ 뿌듯하기도하고 당황스럽기도 하다.

---

큐를 이용한 너비 우선 탐색으로 문제를 풀었다.

문제를 풀기 전에 어떤 섬이 어느 섬들과 연결되어 있는지에 대한 정보를 먼저 정리하고 시작했다.

입력으로 [[1,2] , [2,3]] 이 주어지면

1 -> 2

2 -> 1, 3

3 -> 2

로 정리된 벡터를 하나 만들었다. 이 방법이 아니라면 주어진 roads 라는 벡터를 전부 탐색해야하는데 시간초과가 날것 같았기 때문. (이렇게 풀었는데도 실행시간 보면 당황스럽다. 아래에 있음)

또 방문 여부를 알기 위해 n+1 크기인 int 타입 벡터도 -1로 초기화 시킨 뒤 문제를 풀었다.

 

그 외는 너비 우선 탐색과 동일하다. 방문한 섬을 큐에 넣어주고 현재 섬과 연결되어 있는데 방문하지 않는 섬들을 큐에 넣어주고 몇 번째로 탐색했는지를 체크해준다.

문제자체는 어렵지 않았으나 for문을 그냥 돌려버리면 시간 초과가 나오지 않았을까 한다.

 

< 문제 >

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

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

 

(노트북이라서 문제 그냥 여기까지만 올림.. 마우스도 없음 ㅠㅠ)

 

< 풀이 >

효율성이 더 올라간 수정 코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer;
    vector<int> vec_road(n + 1, -1);

    // 어떤 노드가 어떤 노드와 이어졌는지 정리
    vector<vector<int>> linked_road(n + 1);
    for (auto r : roads)
    {
        int first = r[0];
        int second = r[1];

        linked_road[first].push_back(second);
        linked_road[second].push_back(first);
    }
    
    // 도착지에서부터 얼마나 길이 먼지 계산해줌.
    queue<int> que;
    que.push(destination);
    vec_road[destination] = 0;
    
    // 전체 탐색.
    while (!que.empty())
    {
       int curIdx = que.front();
       que.pop();

       // 현재 인덱스와 이어진 곳들 탐색.
       for (int i = 0; i < linked_road[curIdx].size(); i++)
       {
           int roadIdx = linked_road[curIdx][i];

           // 방문한적 없는 노드라면 큐에 집어넣어줌.
           if (vec_road[roadIdx] == -1)
           {
               que.push(roadIdx);
               vec_road[roadIdx] = vec_road[curIdx] + 1;
           }
       }
     }
    
    for(auto s : sources)
        answer.push_back(vec_road[s]);

    
    return answer;
}

---

기존 코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer;
    vector<int> vec_road(n + 1, -1);

    // 어떤 노드가 어떤 노드와 이어졌는지 정리
    vector<vector<int>> linked_road(n + 1);
    for (auto r : roads)
    {
        int first = r[0];
        int second = r[1];

        linked_road[first].push_back(second);
        linked_road[second].push_back(first);
    }


    // 소스의 개수만큼 너비우선 탐색을 진행함
    for (auto s : sources)
    {
        queue<int> que;

        // 큐에 현재 방문한 인덱스를 넣어줌.
        int curSource = s;
        que.push(curSource);
        vec_road[curSource] = 0;
        answer.push_back(-1);
        // while문을 돌면서 dest에 도착했는지 검사
        while (!que.empty())
        {
            //종료 조건
            int curIdx = que.front();
            if (curIdx == destination)
            {
                answer[answer.size() - 1] = vec_road[curIdx];
                break;
            }
            que.pop();

            // 현재 인덱스와 이어진 곳들 탐색.
            for (int i = 0; i < linked_road[curIdx].size(); i++)
            {
                int roadIdx = linked_road[curIdx][i];

                // 방문한적 없는 노드라면 큐이 집어넣어줌.
                if (vec_road[roadIdx] == -1)
                {
                    que.push(roadIdx);
                    vec_road[roadIdx] = vec_road[curIdx] + 1;
                }
            }

        }
        // 초기화
        for (int i=0; i<vec_road.size(); i++)
            vec_road[i] = -1;
    }
    
    return answer;
}

 

 

기존 코드 결과물

수정 코드 결과물

엄청나게 빨라졌다는걸 알 수 있다!