[HackerRank] BFS - Find the nearest clone

링크

https://www.hackerrank.com/challenges/find-the-nearest-clone/

 

코드

int findShortest(int graph_nodes, vector<int> graph_from, vector<int> graph_to, vector<long> ids, int val) 
{
    //vector<vector<int>> links(graph_nodes + 1, vector<int>());
    map<int, vector<int>> links;

    for (int index = 0; index < graph_from.size(); ++index)
    {
        int fromNum = graph_from[index];
        int toNum = graph_to[index];

        links[fromNum].push_back(toNum);
        links[toNum].push_back(fromNum);
    }

    int sameColorNodesCount = 0;

    for (int index = 0; index < graph_nodes; ++index)
    {
        int color = ids[index];
        if (val == color)
        {
            ++sameColorNodesCount;
        }
    }

    vector<bool> visited(graph_nodes, false);
    const int defaultLength = INT32_MAX;
    int minLength = defaultLength;

    for (int index = 0; index < graph_nodes; ++index)
    {
		if (sameColorNodesCount < 2)
		{
			break;
		}

        int color = ids[index];
		queue<int> numQueue;
		vector<int> lengths(graph_nodes, -1);

        if (val == color && !visited[index])
        {
            numQueue.push(index + 1);
            visited[index] = true;
            lengths[index] = 0;
        }

        bool bFound = false;

        while (numQueue.size() > 0)
        {
            int num = numQueue.front();
            int numIndex = num - 1;
            numQueue.pop();
            vector<int> link = links[num];

            for (int index = 0; index < link.size(); ++index)
            {
                int linkNum = link[index];
                int linkNumIndex = linkNum - 1;

				if (visited[linkNumIndex])
				{
					continue;
				}

				int parentLength = lengths[numIndex];
				int length = parentLength + 1;

                if (ids[linkNumIndex] == val)
                {
                    if (minLength > length)
                    {
                        bFound = true;
                        minLength = length;
                        --sameColorNodesCount;
						break;
                    }
                }

                lengths[linkNumIndex] = length;
                visited[linkNumIndex] = true;
				numQueue.push(linkNum);
            }
        }
    }

    if (minLength == defaultLength)
    {
        return -1;
    }

    return minLength;
}

 

풀이

 

처음에는 같은 색깔인 노드가 몇 개인지 고려를 안 하고 bfs 를 이용해 문제를 풀었었다.

그 결과 정확도에는 문제가 없었으나 몇 개의 테스트 케이스가 시간 초과로 못 풀었다.

해당 케이스들은 모두 노드들 중에 같은 색깔이 없거나, 1개 밖에 없는 경우였다.

 

결론적으로 시간 초과가 난 이유는 같은 색깔의 노드를 찾지 못해서 엄청나게 많은 노드들을 모두 탐색을 하게 되는 경우에 발생하는 것이였다.

 

해결 방법은 처음에 같은 색깔의 노드 갯수를 구한 후 남은 같은 색깔의 노드 갯수가 2개보다 적을 때 찾을 이유가 없으므로 더 이상 찾지 않는 방식이다.

해당 방법은 두 가지 경우로 나뉜다.

• 처음에 같은 색깔의 노드 갯수를 구한 후 같은 색깔의 노드 갯수가 2개보다 많을 경우
  • 해당 노드에서 가장 가까운 같은 색깔의 노드를 찾았을 때 갯수를 감소, 남은 같은 색깔의 노드 갯수가 2개보다 적을 때는 찾을 이유가 없으므로 더 이상 찾지 않는다.
• 처음에 같은 색깔의 노드 갯수를 구한 후 같은 색깔의 노드 갯수가 2개보다 적을 경우
  • 찾을 이유가 없으므로 더 이상 찾지 않는다.