[코딩테스트] [해커랭크] Roads and Libraries

문제

https://www.hackerrank.com/challenges/torque-and-development/problem?isFullScreen=true

1. 도시 개수(n), 도서관 건설비용(c_lib), 도로 건설비용(c_road), 건설 가능 도로 정보(cities)가 매개변수로 주어진다.

2. 최소 건설비용을 들여 모든 도시에서 도서관에 접근할 수 있어야 한다. 이때, 최소 건설 비용을 반환하는 함수를 작성하라.

---

풀이와 주의점

풀이

1. 도로 건설비용이 도서관 건설비용과 같거나, 더 클 경우 각 도시에 도서관을 짓는게 더 적은 비용이 들기 때문에 도시 수 * 도서관 건설비용을 반환한다.

2. 이중벡터로 무방향 그래프를 만들고, 간선 정보를 포함시켜 준다.

3. bfs로 그래프를 순회하며 이어져있는 노드 수를 구한다.

4. bfs가 끝났다면, 해당 노드로부터 이어진 모든 노드를 탐색했다는 뜻이기에 이어진 한 덩어리 개수가 구해진다. => 해당 덩어리에 도서관을 1개 짓고, node - 1 개수만큼 도로를 짓는 비용을 totalCount에 더해준다.

5. 만약 방문하지 않은 노드라면, 3, 4번을 반복한다.

주의점

1. 잘못된 index 접근
   => 1부터 n까지 노드 번호가 입력되는데, 이를 간과해서 에러가 발생했다. 따라서 from과 to를 인접 리스트에 포함시키기 전, 전위 증감 연산자로 1씩 감소시켜서 해결하였다.

2. 명확한 자료형
   => 히든 케이스에서 자꾸 틀려서 코드를 다시 확인하다가, 도시 수 * 도서관 건설비용을 반환할 때 long으로 형변환을 해주지 않았다는 걸 발견했다. totalCost 계산할 때도 마찬가지로 형변환을 해주어야 한다.

---

코드

long roadsAndLibraries(int n, int c_lib, int c_road, vector<vector<int>> cities) 
{ 
    if (c_lib <= c_road)
    {
        return (long)n * c_lib;
    }
    
    vector<vector<int>> adj(n);
    for(int i=0; i<cities.size(); i++)
    {
        int from = cities[i][0];
        int to = cities[i][1];
        
        --from;
        --to;
        
        adj[from].push_back(to);
        adj[to].push_back(from);
    }
    
    long totalCost = 0;
    
    vector<bool> visited(n, false);
    
    for (int i = 0; i<n; i++)
    {
        if (visited[i])
            continue;
            
        queue<int> bfs;
        bfs.push(i);
        visited[i] = true;
        
        long nodeCount = 1;
        
        while(!bfs.empty())
        {
            int current = bfs.front();
            bfs.pop();
        
            for(int next : adj[current])
            {
                if(visited[next])
                    continue;
                
                visited[next] = true;
                nodeCount++;
                bfs.push(next);
            }
        }
        
        totalCost += (long)c_lib + (long)c_road * (nodeCount - 1);
    }
    
    return totalCost;
}