[11주차_목요일] 텀 프로젝트

[yeongleej]

• 사이트 : 백준(BOJ)
• 문제: 텀 프로젝트
• 번호: 9466

### 🤔 시간복잡도 고려사항

### 💡 풀이 아이디어

[baexxbin]

🤔 시간복잡도 고려사항

• 학생 수: 2 ≤ n ≤ 100,000 (10^5)
• O(NlogN)이하
• 풀이한 DFS경우 O(T * N)으로 동작
  • 각 노드는 최대 한번만 방문되며 isfinish된 노드는 방문X

💡 풀이 아이디어

• 그래프의 사이클 찾기
  • dfs와 visited, isfinished를 이용해 그래프 사이클 찾기
  • dfs를 진행하며 방문은 이미 했는데, 아직 해당 노드의 dfs가 끝나지 않았다면 사이클 (역방향 간선)

• dfs(int x) 동작

  • 현재 노드x의 순서 설정
  • 현재 노드x가 선택한 학생 nxt 구하기
    • nxt방문 전이라면 dfs(nxt) 수행
    • 방문은 했는데 dfs가 끝나지 않았으면 사이클이므로 해당 그룹의 학생 수 구하기

  • isfinish로 해당 노드 dfs 종료 처리

    private static void dfs(int x) {
    visited[x] = ++order;           // 현재 지점 몇번째로 방문했는지 체크
    int nxt = choose[x];            // 현재 학생이 선택한 학생
    if (visited[nxt]==0) {          // 선택된 학생을 방문하지 않았으면 dfs진행
        dfs(nxt);
    } else if (!isFinish[nxt]) {    // 방문은 했는데 dfs가 끝나지 않았으면 사이클
        cnt += visited[x] - visited[nxt] + 1;
    }
    
    isFinish[x] = true;
    }

• 처음에 visited로 order처리를 같이해주려고 했었는데, 그렇게되면 이미 방문한 노드의 순서 처리하는 부분이 복잡해짐
• 전역변수로 order는 일정하게 유지하는게 깔끔

[Jewan1120]

🤔 시간복잡도 고려사항

• 2 ≤ n ≤ 100,000 → 10^5 → O(n logn)으로 진행
• 모든 노드를 탐색하는 것이 아닌 방문처리를 이용하여 탐색할 노드의 수를 줄임

💡 풀이 아이디어

• 사이클이 발생하는 모든 노드의 수를 찾는 문제
• 재귀적으로 다음 노드를 탐색하며 이미 방문한 노드를 찾을 때까지 탐색

• 해당 노드에서 방문한 노드를 재 방문하는 경우 사이클이 발생

  • 해당 노드를 기준으로 다시 자기 자신으로 돌아올 때까지 사이클이므로 카운트

    
    // 사이클이 발생하는지 재귀로 탐색
    private static void recurse(int cur) {
    // 방문 처리
    visited[cur] = true;
    int next = arr[cur];    // 현재 학생이 함께하고 싶은 학생
    // 다음 학생이 방문 처리가 되어있지 않다면
    if (!visited[next]) {
    // 다음 학생 탐색
    recurse(next);

  // 방문한 학생인데 사이클이 아직 발생하지 않은 학생일 경우 } else if (!isCycle[next]) { // 현재 학생이 이루는 모든 사이클의 수를 계산 cnt++; while (next != cur) { cnt++; next = arr[next]; } } // 현재 재귀에 있는 모든 학생 사이클 체크 // 다른 재귀에서 해당 학생들은 사이클이 발생할 수 없으므로 isCycle[cur] = true; }

• 하나의 재귀 안에서 사이클이 발생하지 않은 노드들도 사이클이 체크를 해주어야 함
  • 다른 재귀에서는 사이클이 발생할 수 없기 때문

[yeongleej]

🤔 시간복잡도 고려사항

• N <= 100,000

=> 최대 O(N log N)으로 생각해보기

💡 풀이 아이디어

• dfs 탐색으로 사이클 확인하기
  • visited[] : 전체 방문 확인 여부
  • finished[] : 사이클 확인 여부

int next = g[now];
// 아직 방문하지 않음 -> 사이클 발생 X
if(!visited[next]) {
    dfs(next);
}
// 사이클 발생
else {
     // 사이클 내부 방문
     while(!finished[next]) {
        finished[next] = true;
        next = g[next];
        cnt--;     // 사이클 내부 노드는 팀에 속하는 노드
    }
}
// now 노드는 종료 처리
finished[now] = true;

[KodaHye]

🤔 시간복잡도 고려사항

• 2 ≤ 학생의 수(노드의 개수, 간선의 개수) ≤ 100,000 (NlogN 이하 만들기)
• 테스트케이스만큼 DFS 반복했을 때 시간복잡도: T * N

💡 풀이 아이디어

• 사이클을 이루는 학생들의 수를 구해야 됨
• DFS를 통해 문제 풀이
• int[] arr: 함께 하고 싶은 학생 번호 저장
• boolean[] check: 해당 학생을 확인했는지 저장
• boolean[] v: dfs를 수행할 때, 사이클이 발생했는지 확인하는 용도로 사용

static void dfs(int start, int current) {
    if(check[current]) return;

    // 사이클이 발생한 경우
    if(v[current]) {
        check[current] = true;
        cnt += 1;
    }

    v[current] = true;
    dfs(start, arr[current]);

    check[current] = true; // 확인 표시
    v[current] = false; // 원상복구
}

DFS 함수 만들 때, 조건 설정 & 상태 변화 잘 하기

[icegosimperson]

🤔 시간복잡도 고려사항

• n <= 100,000 * T
• O(N log N)

💡 풀이 아이디어

• 팀에 속한 학생들 -> cycle에 포함된 학생 -> cycle 발생 체크
• 자기 자신을 가리키고 있으면 팀 완성 (3) : students[i] == i
• 사이클에 속하지 않은 학생 수 출력 (N-cycleCnt)

• static void dfs (int n){
      if(visited[n]){ // 이미 방문한 노드를 방문한 경우
          cycle[n] = true; // 사이클 발생 의미
          cycleCnt++;
      } else{
          visited[n] = true; // 방문처리
      }
  
      if(!cycle[students[n]]){ // 다음 학생이 팀 결성을 아직 못했을 경우
          dfs(students[n]); // 다시 탐색 시작
      }
      visited[n] = false;
      cycle[n] = true;
  
  }
  }

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: dfs
• 시간복잡도: 시간제한 3 초 2 ≤ n ≤ 100,000 DFS 로 풀이할 경우 O(n+m) > O(n) 으로 풀이가능

💡 풀이 아이디어

• boolean[] visited : 방문 유무
• boolean[] isFinished : 재방문 + 사이클 시도 완료 유무
• boolean[] isGrouping : 팀 프로젝트 가능 유무

1. 학생 한명씩 순회 시작 1-2. 방문하지 않았을 경우 dfs 탐색 진행 1-3. 재방문이지만 이전에 사이클 형성 시도를 완료한 경우 1-4 재방문이고 사이클 형성 시도를 하지 않은 경우 싸이클 만들기 1-5. dfs 탐색이 종료되었을 경우 isFinished 작업 완료 처리
2. isGrouping 에서 프로젝트 팀에 속하지 못한 학생들 카운팅(false)