[LeetCode] 2360. Longest Cycle in a Graph (C++)

문제

방향이 있는 그래프가 주어질 때, 각 노드는 최대 한 개의 나가는 방향의 엣지를 가진다.

엣지들의 길이가 주어졌을 때 길이가 가장 긴 사이클을 구하기.

엣지가 없는경우는 -1의 값을 가진다.

사이클이 없는 경우에는 -1를 리턴

생각할 것

출발 지점과 도착지점이 같은 경우가 사이클에 해당

DFS를 사용해 위 조건을 만족했을 때를 찾기

코드

class Solution {
public:
    int answer = -1;
    void dfs(int start, int next, int len, vector<bool> visited, vector<int> edges){
        visited[next] = true;
        if(start == next) {
            answer = max(answer, len);
        }

        if(edges[next] != -1){
            if(!visited[edges[next]]) {
                dfs(start, edges[next], len + 1, visited, edges);
            }
        }
    }

    int longestCycle(vector<int>& edges) {
        for(int i=0; i<edges.size(); i++){ // 시작 노드
            if(edges[i] == -1) continue;
            vector<bool> visited(edges.size(), false);
            dfs(i, edges[i], 1, visited, edges);
        }

        return answer;
    }
};

위 코드를 실행했을 때 테스트 코드에서는 정답으로 처리되었다.

하지만 제출 했을 때는 동일한 입력값에 대해 시간 초과가 발생했다.

시간을 더 줄일 수 있는 방법이 무엇일까?

개선할 점

1. 각 노드는 한번만 방문해도 된다. → 나가는 길이 하나이기 때문
   1. 현재 노드를 방문하지 않았을 경우에만 수행한다
2. void dfs(int cur, int len, vector<bool>& visited, vector<int>& dfsvisited, vector<int>& edges)
   1. 여기서 &를 붙여서 주소만 전달해주었더니 시간 제한문제가 해결되었다.

코드

class Solution {
public:
    int answer = -1;
    void dfs(int cur, int len, vector<bool>& visited, vector<int>& dfsvisited, vector<int>& edges){     
        if(dfsvisited[cur]){
            answer = max(answer, len - dfsvisited[cur]);
						// 사이클에 포함되지 않는 노드에서 시작했더라도 중간에 방문했던 지점으로 다시 돌아온다면
						// (다시 방문했을 때 - 처음 방문했을 때)의 길이를 계산하여
						// 사이클에 해당하는 부분만의 길이를 알 수 있다.
        }

        if(!visited[cur]) {
            visited[cur] = true;
            dfsvisited[cur] = len;
            int next = edges[cur];
            if(next != -1) {
                dfs(next, len + 1, visited, dfsvisited, edges);
            }
        }
        
        dfsvisited[cur] = 0; // 다시 현재 노드의 길이를 0으로 초기화 해주어야 한다
    }

    int longestCycle(vector<int>& edges) {
        vector<bool> visited(edges.size(), false);
        vector<int> dfsvisited(edges.size(), 0);

        for(int i=0; i<edges.size(); i++){ // 시작 노드
            if(!visited[i]){
                dfs(i, 1, visited, dfsvisited, edges);
            }
        }

        return answer;
    }
};