[알고리즘][X] 텀 프로젝트

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

처음에는 아래와 같이 했다가 틀렸는데 틀린 이유는 완전한 동그라미만 된다고 생각했기 때문이다.

근데 아래 첫번째 원처럼 완전한 원도 될 수 있지만 두번째 원처럼 꽁지가 달릴 수도 있고 세번째 원처럼 해가 될수도 있다. 따라서 완전한 동그라미만 고려한 첫번째 풀이는 틀렸다.

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

public class Main {
	
	static int n;
	static int[] selectedList;
	static boolean[] visited;
	static int ans;
	static int startNum;
	static StringBuilder sb;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		sb = new StringBuilder();
		for (int t = 0; t < T; t++) {
			n = Integer.parseInt(br.readLine());
			StringTokenizer st = new StringTokenizer(br.readLine());
			selectedList = new int[n + 1];
			visited = new boolean[n + 1];
			ans = 0;
			for (int i = 1; i <= n; i++) {
				selectedList[i] = Integer.parseInt(st.nextToken());
			}
			
			for (int i = 1; i <= n; i++) {
				if (visited[i] == true) {
					continue;
				}
				
				startNum = i;
				dfs(i, 1);
			}

			sb.append(ans).append("\n");

		}

		System.out.print(sb);
	}

	public static void dfs(int cur, int count) {
		int next = selectedList[cur];

		if (visited[next]) {
			if (startNum != cur) {
				if (cur == next) {
					count -= 1;
				}
				ans += count;
			}
			return;
		}

		visited[next] = true;
		dfs(next, count + 1);
	}
}

이를 고려한 두번째 풀이에서는 시간초과가 났다. 그 이유는 for문 안에서 int[n+1]을 만들기 때문이다. 그렇게 되면 O(n^2)이 되어서 시간초과가 발생한다. 이를 우회할 수 있는 방안이 필요했다.

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

public class Main {

  static int n;
  static int[] selectedList;
  static boolean[] visited;
  static int[] stored;
  static int ans;
  static int startNum;
  static StringBuilder sb;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.parseInt(br.readLine());
    sb = new StringBuilder();
    for (int t = 0; t < T; t++) {
      n = Integer.parseInt(br.readLine());
      StringTokenizer st = new StringTokenizer(br.readLine());
      selectedList = new int[n + 1];
      visited = new boolean[n + 1];
      ans = n;
      for (int i = 1; i <= n; i++) {
        selectedList[i] = Integer.parseInt(st.nextToken());
      }

      for (int i = 1; i <= n; i++) {
        if (visited[i] == true) {
          continue;
        }
        stored = new int[n + 1];
        stored[i] = 1;
        visited[i] = true;
        dfs(i, 2);
      }

      sb.append(ans).append("\n");

    }

    System.out.print(sb);
  }

  public static void dfs(int cur, int count) {
    int next = selectedList[cur];
    
    if (stored[next] != 0) {
      ans -= count - stored[next];
      return;
    }

    if (visited[next]) {
      return;
    }
    
    stored[next] = count;
    visited[next] = true;
    dfs(next, count + 1);
  }
}

세번째 풀이는 그렇게 탄생했다. 공간을 매번 할당하지 않는 대신에 stored에 저장된 숫자값이 이번 for문에 대한 것임을 나타내기 위해 전역적으로 계속 증가하는 inc 변수를 두었고 dfs가 시작되는 시점에서의 inc의 값을 기준점으로 dfs를 돌렸다. 그렇게 한 결과 시공간 모두를 절약할 수 있었다.

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

public class Main {

  static int n;
  static int[] selectedList;
  static boolean[] visited;
  static int[] stored;
  static int ans;
  static int startNum;
  static int inc;
  static StringBuilder sb;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.parseInt(br.readLine());
    sb = new StringBuilder();
    for (int t = 0; t < T; t++) {
      n = Integer.parseInt(br.readLine());
      StringTokenizer st = new StringTokenizer(br.readLine());
      selectedList = new int[n + 1];
      visited = new boolean[n + 1];
      stored = new int[n + 1];
      inc = 1;
      ans = n;
      for (int i = 1; i <= n; i++) {
        selectedList[i] = Integer.parseInt(st.nextToken());
      }

      for (int i = 1; i <= n; i++) {
        if (visited[i]) {
          continue;
        }

        inc += 1;
        stored[i] = inc;
        visited[i] = true;
        dfs(i, inc);
      }

      sb.append(ans).append("\n");

    }

    System.out.print(sb);
  }

  public static void dfs(int cur, int criteria) {
    int next = selectedList[cur];
    
    if (stored[next] >= criteria) {
      ans -= inc - stored[next] + 1;
      return;
    }

    if (visited[next]) {
      return;
    }

    inc += 1;
    stored[next] = inc;
    visited[next] = true;
    dfs(next, criteria);
  }
}