[해커랭크] Find the nearest clone (C++)

문제 링크: www.hackerrank.com/challenges/find-the-nearest-clone/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=graphs

Find the nearest clone | HackerRank

1. 주의할 점

- BFS를 통해 해결하여 TLE가 나지 않도록 한다

- 방문여부를 기록해둔다

 

2. 구현

- 모든 간선에 대한 정보를 V[] 벡터에 담는다

- Idx: 현재 Node번호, Val: 거친 간선의 개수, Org: 시작 Node의 구조체를 지닌 큐를 생성한다

- Dist[]배열을 통해 각 Node까지의 거리를 저장하며, 초기값은 Max로 초기화한다

- Val 색과 같은 색을 가진 Node를 큐에 넣는다

- BFS를 수행하며, 다음으로 이동하려는 Node가 아직 한 번도 방문하지 않은 경우, 다음 Node를 큐에 넣는다

- 다음으로 이동하려는 Node가 이미 방문한 경험이 있는 경우, 현재 거쳐간 간선의 개수 CV와 비교하여 이전에 뻗어왔던 Node로부터 되돌아가지 않도록 설정하기 위해 Dist[next] > cv-1 인 경우에만 비교를 한다.

- 위의 조건을 만족한 경우, 다음 Node가 Val과 색이 같으며, 시작 Node가 아니라면 Result값을 비교하여 갱신한다

- Result값이 한번도 갱신되지 않은 경우, -1을 Return한다

#define MAX 987654321
#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

// Complete the findShortest function below.

/*
 * For the unweighted graph, <name>:
 *
 * 1. The number of nodes is <name>_nodes.
 * 2. The number of edges is <name>_edges.
 * 3. An edge exists between <name>_from[i] to <name>_to[i].
 *
 */
 struct info{
     int idx, val, org;
 };
 info tmp;
 int dist[1000001];
 vector<int> v[1000001];
 
int findShortest(int graph_nodes, vector<int> graph_from, vector<int> graph_to, vector<long> ids, int val) {
    // solve here
    int result = MAX;
    for(int i=0;i<graph_from.size();i++){
        int a = graph_from[i];
        int b = graph_to[i];
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i=1;i<=graph_nodes;i++)
        dist[i]=MAX;
    queue<info> q;
    tmp.val=0;
    for(int i=0;i<ids.size();i++){
        if(ids[i]==val){
            tmp.idx = i+1;
            tmp.org = i+1;
            q.push(tmp);
            dist[i+1]=0;
        }
    }
    while(!q.empty()){
        int cidx = q.front().idx;
        int cv = q.front().val;
        int co = q.front().org;
        q.pop();
        for(int i=0;i<v[cidx].size();i++){
            int next = v[cidx][i];
            if(dist[next]==MAX){        //아직 방문하지 않은 경우
                dist[next] = cv+1;
                tmp.idx = next;
                tmp.val = cv+1;
                tmp.org = co;
                q.push(tmp);
            }
            else {
                if(dist[next]>cv-1 && ids[next]==val && next!=co)       //방문했던 경우 + 뻗쳐온 경로가 아닌 경우
                    result = min(result,dist[next]+cv+1);  
            }          
        }
    }
    if(result == MAX) result = -1;
    return result;
}