[백준] DFS - 9466번 텀 프로젝트 (Java)

문제링크

9466번: 텀 프로젝트

 

접근한 방법

• dfs

 

---

풀이방법

참고한 블로그

• dfs문제를 풀 때 boolean 자료형으로 방문여부(visited 배열)만 체크했는데,
  이 문제는 그 노드의 깊이의 탐색이 끝났는지(finished 배열)도 체크를 해야했다.
•  dfs 메소드를 선언하여 파라미터를 노드번호로 받는다.
  • 현재 노드를 방문 처리하고, 그 노드에 이어져있는 다음 번호 방문 여부를 체크한 후, 방문을 진행한다.
  • 일단 탐색이 끝난 여부 처리하는 걸 무시하고 생각했을 때 노드와 이어져있는 모든 노드의 방문이 끝나면 (재귀함수가 종료되면)
    현재 노드의 탐색이 끝났다고 처리한다.
  • 여기서 뽀인뜨는 이어져있는 노드의 탐색이 아직 끝나지 않았는데, 이미 방문한 노드를 만난거라면
    그 연결은 cycle인 것이다.
    • 출력은 연결의 개수를 구하는 것이 아니라, 팀이 이루어지지 못한 학생수를 구하는 것이므로
      현재 연결에 속해있는 노드의 개수를 반복문을 사용하여 구해주어야한다.
      
      
  • 예시) 더보기 클릭

    

---

소스코드 작성 방법

• 학생의 수, 학생들 번호의 집합 (노드가 연결된 정보), 노드 방문 여부, 노드 탐색의 마지막 여부, 팀이 이루어지는 횟수를 전역 필드로 선언한다.
• 입력의 노드 시작번호가 1 이므로, 배열의 크기는 모두 n+1로 초기화 시켜준다.
• dfs 메소드의 인자를 노드 번호(cur)로 받는다. (cur : 현재 노드를 나타냄)
  • vistied[cur] = true로 하여 방문 처리
  • next 필드를 선언하여 다음에 방문할 노드 번호를 저장
  • visited[next]가 false로 아직 방문하지 않은 노드라면 dfs 메소드를 재귀적으로 호출하여 방문수행
  • vistied[next]가 true로 방문한 노드이며, finished[next]가 false 로 노드 탐색의 끝이 아니라면
    해당 노드의 연결은 cycle이므로 연결에 속해있는 노드의 개수를 구한다.
    • 반복문을 이용하여 노드의 개수를 구해준다 (이 반복문은 나에게 조금 생소하였다..하하..)
      - 시작조건 : next노드 ; 반복조건 : 현재 노드 값이 아닐 때 ; 다음값 : next노드에 연결된 노드 -
      반복 시작을 next노드 부터  현재 노드가 아닐때까지 하므로 반복문이 종료된 후, 현재 노드도 더해주어야한다.
    • 예시) 더보기 클릭

 

• 이어져있는 노드의 방문이 끝나면 (재귀 호출이 끝나면) finished[cur] = true 로
  현재 노드와 연결된 노드들의 탐색이 끝났음을 처리해준다.
•  
• solution 메소드에서 1번 노드부터 마지막 번호 노드까지 탐색을 수행한다.
  • 여기서 탐색할 노드를 방문했는 지 먼저 검사하지 않으면,
    이전 번호의 노드에서 이미 방문을 한 경우가 있을 때 중복 탐색을 하기 때문에
    방문여부를 먼저 검사하여 방문하지 않은 노드만 탐색을 수행한다.

 

소스코드

package baekjoon.dfs_bfs;
import java.io.*;
import java.util.StringTokenizer;

public class Q_9466_TermProject_20210519 {
    static int n; // 학생의 수
    static int[] map ; // 학생들 번호의 집합
    static boolean[] visited; // 노드 방문 여부
    static boolean[] finished; // 노드 탐색의 마지막 여부
    static int result; // 팀이 이루어지는 횟수

    public static void solution() {
        for (int index = 1; index <= n; index++) {
            if(!visited[index])
                dfs(index);
        }
    }

    public static void dfs(int cur){
        // 방문 처리
        visited[cur] = true;
        // 다음에 방문할 노드
        int next = map[cur];

        // 다음 노드를 아직 방문하지 않았다면 방문 수행
        if(!visited[next]){
            dfs(next);
        }

        // cur이 갖고 있는 값을 방문하였는데 노드 끝이 아니라면 cycle
        if(visited[next] && !finished[next]){
            // cycle 내의 학생 수 더해주기
            for(int temp = next ; temp != cur ; temp = map[temp])
                result++;
            // 자기 자신
            result ++;
        }

        finished[cur] = true;

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(br.readLine());
        for(int i=0 ; i<t ; i++) {
            n = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            map = new int[n + 1];
            visited = new boolean[n + 1];
            finished = new boolean[n + 1];
            result = 0;
            for (int j = 1; j <= n; j++) {
                map[j] = Integer.parseInt(st.nextToken());
            }
            solution();
            System.out.println(n - result); // 팀에 속하지 못한 학생 수

        }


        br.close();
        bw.close();
    }
}