23.03.24. 풀었던 문제들

Leetcode 1466. Reorder Routes to Make All Paths Lead to the City Zero

 이 문제는 0부터 DFS를 시작한다고 생각하면 아주 쉽게 풀린다. 비록 주어진 edge는 directed이지만 이를 indirected로 바꾼다. 대신 outgoing인지 incoming인지에 대한 flag를 하나 둔다. 이후 0부터 DFS 또는 BFS를 하고, edge가 incoming일 때만 해당 edge를 바꾸어 주면 된다.

// Runtime 342 ms Beats 93.65%
// Memory 106.6 MB Beats 74.70%

struct edge{
    int next;
    bool isOutgoing;
};

class Solution {
public:
    int answer;
    vector<vector<edge>> edges; // edges[i] : ith vertex가 가리키는 {vertex, 나가는지 여부} vector
    vector<bool> visited;
    void DFS(int cur){
        for(edge e : edges[cur]){
            if(!visited[e.next]){
                visited[e.next] = true;
                if(e.isOutgoing) answer++; // 나가는 edge인 경우 뒤집어 주어야 함
                DFS(e.next);
            }
        }
    }
    int minReorder(int n, vector<vector<int>>& connections) {
        // init
        answer = 0;
        edges.resize(n);
        for(vector<int> &connection : connections){
            edges[connection[0]].push_back({connection[1], true});
            edges[connection[1]].push_back({connection[0], false});
        }
        visited.resize(n);
        fill(visited.begin(), visited.end(), false);

        visited[0] = true;
        DFS(0);

        return answer;
    }
};

 

시간복잡도

 DFS이므로 O(V + E)인데, E = n-1이고 V = n이므로 O(n)이다.

 

공간복잡도

 edges에 O(E), visited에 O(V). 마찬가지로 O(n)이다.

 

후기

 leetcode에는 코테 스타일로 귀찮은 구현 문제가 많이 없어서 아쉽다. hard를 풀어봐야 하나?