백준 - 텀 프로젝트

문제 링크 ▶︎ 텀 프로젝트

문제 파악

문제에서 주어지는 정수 배열에 대해서 각 index(실제로는 index+1)에 해당하는 학생이 그 밸류에 해당하는 학생을 지목해서 단방향으로 그래프가 그려진다고 생각할 수 있다. 그러면 사이클이 형성이 되면 팀이 구성되는것이고, 혼자 지목해서 혼자하는 것도 팀이라고 볼 수 있다. 그러면 혼자 팀도 아니고 사이클에 포함되지않은 index의 갯수가 정답의 수라고 볼 수 있다. 그래서 사이클을 형성하는 로직을 통해서 전체 학생 수에서 사이클에 포함된 수를 빼주면서 정답을 찾아야한다.

접근 방법

1. Map<Integer, Integer>를 만들어서 현재 index의 학생이 어떤 학생을 지목했는지 단방향 그래프를 만들고, 방문 배열을 만들어서 방문 처리 로직도 만들어야한다. 그리고 만약 혼자 팀을 하는 index에 대해서는 팀이 구성되었으므로 cnt++하고 방문처리도 해준다.

2. 그러고 1~n까지 돌면서 방문하지 않은 index에 접근해서 List<>에 path를 추가한다. 그리고 방문처리도 하고 cycle 메서드를 수행한다.

3. 사이클 메서드는 현재 List path에서 제일 최신 정보를 빼서 다음 노드가 어디로 갈지 정한다. 만약 다음에 갈 곳이 이미 방문한 곳이라면 더 하지 않아도된다. 그리고 이때까지 저장된 path에서 다음 방문할 곳의 기록이 남았다면 그 길이만큼 사이클이 형성된 것이고 cnt에 그 길이만큼을 추가해주고 나온다.

4. 만약 방문하지 않은 곳이라면 쭉 이어서 방문하면 된다. 이때 모두 다 순회가 끝난다면 사이클이 형성된만큼 cnt가 추가될 것이라 전체 수에서 cnt를 빼주면 정답이 된다.

코드 구현

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

public class Main {
    public static int t, n, cnt;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        t = Integer.parseInt(st.nextToken());
        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            Map<Integer, Integer> data = new HashMap<>();
            cnt = 0;
            boolean[] visited = new boolean[n + 1];
            for (int from = 1; from <= n; from++) {
                int to = Integer.parseInt(st.nextToken());
                data.put(from, to);
                if (from == to) {
                    cnt++;
                    visited[to] = true;
                }
            }
            for (int j = 1; j <= n; j++) {
                if (!visited[j]) {
                    List<Integer> path = new ArrayList<>();
                    path.add(j);
                    visited[j] = true;
                    cycle(path, data, visited);
                }
            }
            System.out.println(n - cnt);
        }
    }
    public static void cycle(List<Integer> log, Map<Integer, Integer> data, boolean[] visited) {
        int from = log.get(log.size() - 1);
        int to = data.get(from);
        if (visited[to]) {
            for (int i = 0; i < log.size(); i++) {
                if (log.get(i) == to) {
                    cnt += (log.size() - i);
                    break;
                }
            }
            return;
        } else {
            log.add(to);
            visited[to] = true;
            cycle(log, data, visited);
        }
    }
}

개선 사항

cycle 메서드에 진입하기 전에 List를 계속 생성하기 때문에 메모리가 낭비될 가능성이 있다. 그래서 따로 for (int i = to; i != from; i = data.get(i)) 로 이때까지의 로그를 찾아보는 방법도 있다.