void swap(int& a, int& b){
    int tmp = a;
    a = b;
    b = tmp;
}

int Moves(vector<int> arr) {
    int cnt = 0;
    int len = arr.size();
    
    int left = 0, right = len - 1;
    while(1){
        
        while(arr[left] % 2 == 0){ // 홀수 찾기
            left += 1;
        }
        
        while(arr[right] % 2 != 0){ // 짝수 찾기
            right -= 1;
        }
        
        if(left >= right) break;
        
        swap(arr[left], arr[right]);
        left += 1;
        right -= 1;
        cnt += 1;
        
        
    }
    return cnt;

}

투 포인터를 이용해서 양쪽 끝에서부터 홀수와 짝수를 찾아서 서로 자리를 바꿔준다.

이중 포문으로 하면 N^2이 나옴 근데 그 방식은 느릴 뿐만 아니라 반드시 최소 횟수로 교환하지 않음, 왜냐하면 왼쪽에서부터 첫번째 홀수륵 찾았을 때 가장 가까운 짝수랑 바꾸기 때문에 뒤로 돌아간 홀수가 다시 그 뒤의 짝수랑 바뀌는 문제가 있음. 이를 위해서 두번쨰 포문은 뒤에서 부터 하면 해결될 것 같으나, 그런 방식이라면 투포인터를 쓰는게 더 빠를 것 같음

O(N)

bool visited[3001];
vector<int> path;
bool cycle = false;
unordered_set<int> cycle_set;

void dfs(int cur, int parent, vector<vector<int>>& adj_list) {
    visited[cur] = true;
    path.push_back(cur);
    
    for (int to : adj_list[cur]) {
        if (!visited[to]) {
            dfs(to, cur, adj_list);
            if (cycle) return; 
        }
        else if (parent != to) {
            for (int n = path.size() - 1; n >= 0; n--) {
                cycle_set.insert(path[n]);
                if (path[n] == to) break;
            }
            cycle = true;
            return;
        }
    }
    
    path.pop_back();
}

int getDistance(int node, vector<vector<int>>& adj_list, const unordered_set<int>& cycle_set) {
    queue<pair<int, int>> Q;
    Q.push({node, 0});
    
    bool V[3001] = {};
    V[node] = true;
    
    while (!Q.empty()) {
        int cur = Q.front().first;
        int dist = Q.front().second;
        Q.pop();
        
        // 현재 노드의 인접 노드 탐색
        for (int to : adj_list[cur]) {
            if (!V[to]) {
                if (cycle_set.count(to)) {
                    return dist + 1;
                }
                V[to] = true;
                Q.push({to, dist + 1});
            }
        }
    }
    
    return -1;
}

vector<int> nodeDistance(int s_nodes, vector<int> s_from, vector<int> s_to) {
    int s_edges = s_from.size();
    vector<int> res(s_nodes);
    
    vector<vector<int>> adj_list(s_nodes + 1);
    

    for (int i = 0; i < s_edges; i++) {
        int from = s_from[i];
        int to = s_to[i];
        adj_list[from].push_back(to);
        adj_list[to].push_back(from);
    }
    
    //DFS로 사이클 탐지
    dfs(s_from[0], -1, adj_list);
    
    //각 노드에 대해 사이클까지의 최소 거리 계산
    for (int n = 1; n <= s_nodes; n++) {
        if (cycle_set.count(n)) {
            res[n - 1] = 0;
        } else {
            res[n - 1] = getDistance(n, adj_list, cycle_set);
        }
    }
    
    return res;
}

dfs로 싸이클을 구성하는 노드를 탐지하고 그외의 노드들이 싸이클 안의 노드까지 가는데 걸리는 거리를 bfs로 최단거리로 계산해주면됨.

dfs

• 역순으로 하는 이유 : 외부 노드에서 dfs를 시작했을 수 있으니까

• 현재 노드와 연결된 노드중에 직전 노드가 아닌 방문한 노드와 연결되어 있다면 싸이클이 존재함.

• 문제는 그 과정에서 dfs는 재귀 함수가 리턴되고 다시 돌아와서 남은 노드들을 탐색하는 방식이라 싸이클을 한번 찾고난 뒤에도 시작 노드랑 끝노드가 다시 싸이클로 인식됨

• 1 - 2

  1 - 2
  |   |
  4 - 3
  이 경우 1 - 2 - 3 - 4
  하고 1- 4
  가 두번나올거임
  

• 간선 리스트 만들었고

• bfs는 노드 번호와 거리를 둘다 넣음

O(V + E)