[C++][대체 경로] 구름톤 챌린지 4주차 학습 일기 (2)

서론

오늘도 문제 풀다 번아웃이 왔다.

4시간 동안 풀었다...

4일 차 대체 경로

문제 : 요약이 힘들어 사진으로 대체

 

가장 짧은 거리를 찾는것임으로 BFS를 이용하여서, 하나의 길이 만들어진다면 종료되도록 구성하였다.

단순한 BFS를 구현하면 Timeout이 발생함으로 distace 배열을 통하여 거리를 저장하여 계산을 구현하였다.

 

 

◆코드 전문◆

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int node, edge, start, endNode;

int bfs(int day,vector<vector<int>> &edgeList)
{
    if (day == start || day == endNode)
    {
        return -1;
    }

    vector<int> distance(node + 1, -1);
    vector<int> parent(node + 1, -1);
    queue<int> que;

    que.push(start);
    distance[start] = 1;
    parent[start] = 0;

    while (!que.empty())
    {
        int here = que.front();
        que.pop();
			
        for (int i : edgeList[here])
        {
            if (i == day)
                continue;
            if (distance[i] == -1)
            {
                que.push(i);
                distance[i] = distance[here] + 1;
                parent[i] = here;
            }
        }
    }
    return distance[endNode];
}

int main()
{
    cin >> node >> edge >> start >> endNode;
    vector<vector<int>> edgeList(node + 1, vector<int>());
    for (int i = 0; i < edge; i++)
    {
        int bufA, bufB;
        cin >> bufA >> bufB;
        edgeList[bufA].push_back(bufB);
        edgeList[bufB].push_back(bufA);
    }

    for (int i = 1; i <= node; i++)
    {
        cout << bfs(i,edgeList) << "\n";
    }
    return 0;
}

양방향 그래프인 점을 고려하여 edgeList(인접 리스트)를 구현하였다.

이후 bfs함수에서 -1이 되는 조건들(시작노드, 끝노드 공사 중)을 걸러내고 que의 top에서 갈 수 있는 곳을 탐색하였다.

부모와 거리는 parent와 distance에 저장하여 return distance[endNode]를 통해서 endNode까지의 길이를 return 해주었다. 

길이 없는경우 배열이 -1로 초기화되어 있기 때문에 문제없이 출력된다.

어려웠던 점

문제를 보니 그래프 구현을 통해서 쉽게 풀 수 있는 재밌는 문제라고 생각했는데, 아니었다.

항상 그래프 문제를 풀 때마다 발목을 잡는 상식이 있는데, "BFS는 빠른 시간 내에 정보를 찾을 순 있지만, 그게 최선의 답은 아닐 수 있다."이다.

이 문제에선 거리가(depth) 짧은 것이 무조건 정답이기 때문에 BFS가 유리하나, 나는 위에 언급한 말 때문에 DFS로 처음에 구현하였다. 

그러고 구현적인 문제로 1시간 소요하고, DFS 최적화를 하는데 1시간을 소요하고, 도시의 개수만큼 DFS을 하는 것이 문제인가 싶어 한번에 모든 경로를 구하고, 반복문을 통해서 i를 가지지 않는 길중 짧은 길을 출력하는 방법도 썼지만 틀렸다.

조언을 구하니 BFS나 다익스트라로 푸는 이야기를 듣고서 다시 짰지만, 그럼에도 Timeout이 나왔다. 

매번 기초 지식이 부족한 것을 통감하는 이번주이다.

 

배운 점

반복문을 사용함에 있어서 새로운 방법을 사용하여 익숙해지는 시간을 가졌다.

또한 전역변수 선언을 하고 초기화를 main에서 동적으로 하는 방법을 배워서, 함수의 매개변수로 전달하지 않고 빠르게 코딩하는 법을 배웠다. (vector)

느낀 점

구현 자체는 시간 내로 할 수 있겠다는 자신감은 생긴다. 하지만 구현 알고리즘이 잘못되면 시간이 최소 1시간은 걸리는 만큼 어떤 알고리즘을 사용하면 효과적으로 풀 수 있는지를 고려하는 것이 중요하다고 생각된다.

그리고 구름 TC를 돌리면 꼭 몇 개는 오류가 나오는데, 이를 피하기 위해서 내가 문제 구현을 추상화를 적절하게 했는지, 잘 이해했는지에 대해 더 검토하게 된 거 같다.

 

그래도 구름톤이라 악으로 깡으로 버티는 거 같긴 한데...