[Java] BOJ9466, 백준 - 텀 프로젝트

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

9466번: 텀 프로젝트

1. 문제 풀이
떠오르는 풀이는 간단합니다.
(조를 만들지 못하는 학생을 탈락했다고 표현)
인덱스 순서대로 진행하고, 현재 배열값이 가르키는 학생 번호로 이동해서 조를 짤 수 없으면 탈락된 학생들의 숫자를 더해주고, 하나의 사이클이 만들어졌다면 탈락하는 학생들이 없다는 이야기입니다. 사이클 여부는 맨 처음 학생의 번호와 비교했습니다.
boolean[] visit배열을 이용하여 방문한 학생을 중복해서 방문하지 않도록 처리해주었습니다.

만약 중복해서 방문하는 경우는 사이클이 만들어질 수 없는 경우입니다.

if (visit[now]) {
	// 이미 방문했었던 칸을 만난다.
	ans += cnt - 1;
	return;
}

 

또한, 만약 혼자 조를 하고싶은 학생과 마주하는 경우 이전에 사이클을 만들던 학생들은 모두 탈락입니다.

if (students[now] == now) {
	// 혼자 할꺼면 이전것들은 나가리
	ans += cnt - 1;
	return;
}

 

 

 

여기까지 구현하였다면 한 가지 문제가 발생합니다.
바로

6
2 3 4 5 6 4

의 경우 중간에서 사이클이 만들어지는데, 이를 구분할 방법이 없는 것입니다.
이를 위해 int[] currVisit 배열을 사용하여 해당 사이클에서의 순서와 학생번호를 기록해주었습니다.

만약 진행하다가 currVisit에서 만난 적 있는 학생을 만나면 사이클이 만들어진 것입니다.

중간부터 사이클이 만들어지는 경우를 위해서 배열에 학생순서를 저장해두었습니다.

if (currVisit[now] != 0) {
	// 이번 사이클에서 방문했던 곳을 만났다면 사이클 종료
	ans += currVisit[now] - 1;
	return;
}

 

2. 부딪혔던 문제들 및 해결법
처음에는 새로운 학생을 방문할 때마다 currVisit배열의 값을 초기화해주었기 때문에

currVisit = new int[n+1];
Arrays.fill(currVisit, 0);

등의 방법을 사용해주었으나, 이 때 배열 초기화 시에 드는 시간만 O(N*N)이 걸리기 때문에 시간초과가 발생합니다.
그래서 재귀를 진행하면서 다시 0으로 돌려주는 방식을 사용하였습니다.

 

currVisit[now] = cnt;
go(students[now], cnt + 1);
currVisit[now] = 0;

(이러면 사용했던 배열 만큼의 크기만 발생하게 되어, O(N).)

 

ans를 더해주고 return을 하는 작업이 반복되기 때문에 ans를 반환하는 int형 함수로 짜고 싶었는데, 위와 같은 방법으로 currVisit배열을 초기화해주니 return go();를 할 수 없어서, void 함수로 만들었다.

이에 관한 좋은 해결법이 있다면 댓글로 남겨주세용

 

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

public class Main {

    private static int[] students;
    private static boolean[] visit;
    private static int[] currVisit;
    private static int ans;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int TC = Integer.parseInt(br.readLine());
        for (int tc = 0; tc < TC; tc++) {
            int n = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            students = new int[n + 1];
            currVisit = new int[n + 1];
            visit = new boolean[n + 1];
            for (int i = 1; i <= n; i++) {
                students[i] = Integer.parseInt(st.nextToken());
            }

            ans = 0;
            for (int i = 1; i <= n; i++) {
                if (!visit[i]) {
                    go(i, 1);
                }
            }
            System.out.println(ans);
        } // end TC
    }

    private static void go(int now, int cnt) {
        if (currVisit[now] != 0) {
            // 이번 사이클에서 방문했던 곳을 만났다면 사이클 종료
//            System.out.println("돌았다" + (currVisit[now] - 1));
            ans += currVisit[now] - 1;
            return;
        }
        if (visit[now]) {
            // 이미 방문했었던 칸을 만난다.
//            System.out.println("못한다 " + (cnt - 1));
            ans += cnt - 1;
            return;
        }
        if (students[now] == now) {
            // 혼자 할꺼면 이전것들은 나가리
//            System.out.println("혼자한다" + (cnt - 1));
            ans += cnt - 1;
            return;
        }
        visit[now] = true;
        currVisit[now] = cnt;

        go(students[now], cnt + 1);
        currVisit[now] = 0;
    }
}