[Baekjoon] 텀 프로젝트 - Java

문제

https://www.acmicpc.net/problem/9466

 

풀이

학생들의 선택에 사이클이 되는 경우 팀이 결성되는데, 결성 되지 않은 팀원들을 구하는 문제이다.

 

이 문제에서는 2가지 체크하는 배열이 필요하다.

1. 노드를 방문 체크 배열

2. 팀이 꾸려졌는지 체크 배열(팀이 결성된 학생을 세지 않기 위함이다.)

 

다음 노드가 무조건 1개이므로, dfs를 사용하는 것이 적절하다고 판단했다.

dfs를 수행하면서 현재 정점에서 다음 정점에 대한 방문 여부를 생각했을 때

현재 정점은 방문되지 않았지만  다음 정점이 방문되었다면 무조건 사이클이 도는 것이라고 할 수 있다.

 

그러면 팀 결성 여부를 확인하고

팀이 결성되지 않았었다면, 사이클이 도는 학생들의 수를 센다.

 

이 풀이는 팀이 결성되지 않았으면서 + 사이클이 있으면 => 수를 센다의 개념이다.

만약에 사이클이 돌지 않았으면 순회한 노드들이 팀을 꾸릴 수 없는 것이므로, 팀이 결성된 체크는 해줘야한다.

 

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

import java.util.StringTokenizer;

public class Main {
    static int cnt;

    static int[] next;
    static boolean[] visited;
    static boolean[] isTeam;

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

        int tc = Integer.parseInt(br.readLine());

        StringTokenizer st;

        StringBuilder sb = new StringBuilder();

        while (tc > 0) {
            int n = Integer.parseInt(br.readLine());

            next = new int[n + 1];
            visited = new boolean[n + 1];
            isTeam = new boolean[n + 1];

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

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

            cnt = 0;

            for (int i = 1; i <= n; i++) {
                dfs(i);
            }

            sb.append(n - cnt).append("\n");

            tc--;
        }

        System.out.print(sb);

        br.close();
    }

    static void dfs(int start) {
        visited[start] = true;

        int nextPos = next[start];

        if (!visited[nextPos]) {
            dfs(nextPos);
        } else {
            int curPos = nextPos;

            if (!isTeam[curPos]) {
                cnt++;

                while(curPos != start) {
                    cnt++;
                    curPos = next[curPos];
                }
            }
        }

        isTeam[start] = true;
    }
}

 

실행결과