[PS] BOJ9466 텀프로젝트 ( DFS ) with JAVA

9466번: 텀 프로젝트

 

 

◎ 문제풀이

 

문제요약 : 학생들이 원하는 팀원 정보가 그래프로 주어질 때, 싸이클을 형성하면 팀으로 구성된다. 싸이클을 형성하지 못하는 팀원의 수를 구하라.

 

문제풀이 :

- 방향그래프에서 싸이클을 찾는 문제이므로 DFS를 발상하였다.( 무방향 그래프에서 싸이클을 찾는 문제는 UNION-FIND 알고리즘 사용 )

- 방문여부 배열과 싸이클 여부 배열로 DFS 로직을 구성하였다.

- 탐색과정에서 이미 방문한 노드를 다시 접근하면 싸이클이 형성된다.

- 싸이클 여부가 결정된 곳은 DFS 호출하지 않는다.

 

4(방문 O) → 5(방문O) → 6(방문O) → 7(방문O) →

4(방문O, 싸이클O) → 5(방문O, 싸이클O) → 6(방문O, 싸이클O) → 7(방문O, 싸이클O) →

4(방문O, 싸이클O, DFS 종료)

 

고려하지 못한 점:

 

방문여부 배열은 DFS 호출마다 초기화 해주어야 한다. 그래서 DFS 메소드 파라미터에 new 연산자로 방문여부배열을 생성하여 넘겨주었더니 시간초과가 발생하였다. 정답코드에서도 방문여부 배열을 파라미터로 동적생성하여 넘겨주니 시간초과가 발생하였다. 학생수가 최대 10만이라 메모리 초과를 예상하기는 했지만 시간초과가 발생해서 DFS 로직상의 문제인줄 알았다.

 

◎ 코드

package org.example.dfs;

import java.io.*;
import java.util.*;

//BOJ9466 텀프로젝트 ( 방향그래프에서 싸이클 찾기 )
public class Dfs9 {

    public static int n,ans;
    public static int[] arr;
    public static boolean[] isDone,visited;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        while(t-- > 0){

            ans = 0;
            n = Integer.parseInt(br.readLine());
            arr = new int[n+1];
            isDone = new boolean[n+1];
            visited = new boolean[n+1];

            StringTokenizer st = new StringTokenizer(br.readLine());

            for(int i=1;i<=n;i++){
                arr[i] = Integer.parseInt(st.nextToken());
            }

            for(int i=1;i<=n;i++){
                if(!isDone[i]) {
                    dfs(i);
                }

            }
            System.out.println(n-ans);

        }

    }

    public static void dfs( int curr ){

        if(visited[curr]){
            isDone[curr] = true;
            ans++;
        }

        else {
            visited[curr] = true;
        }

        int next = arr[curr];
        if(!isDone[next]){
            dfs(next);
        }

        visited[curr] = false;
        isDone[curr] = true;
    }
}