백준 [자바 java] 9466번 : 텀 프로젝트

문제설명

n명의 사람들이 있고, 이 사람들이 원하는 팀원이 주어진다고 할 때, 그 어떤 팀에도 속하지 못하는 사람이 있을 수 있다. 이 사람들의 명수를 구하여라

 

풀이

처음에는 혼자 팀을 하고싶어하는 사람과 팀을 하고싶어하는 사람들을 팀에 속하지 못하는 사람으로 분류하고, 또 그 사람과 팀을 원하는 사람을 제외하고.... 이런식으로 문제를 풀었는데 광탈을 해버렸다.

 

그래서 여러 반례를 찾아보니, 스스로와 팀을 원하는(혼자 팀을 원하는) 사람들이 없는데도, 팀을 이루지 못하는 경우도 있었다.

사이클에 포함되지 못하는 경우! 그래서 이 경우를 제외해야한다.

 

역시,, 가능한 사람들을 보고 빼는게 맞는거같다. 이렇게 하니까 너무 많은 반례를 지나친다

 

그래서 while문을 통해 계속해서 탐색하다가 이미 방문한 노드를 마주치면 현재 탐색중인 노드와 그 노드가 일치하는지 여부를 보는 방식으로 풀어봤는데 시간초과가 나왔다..

 

그래서 다른 사람들 풀이를 좀 훔쳐봤는데 다들 dfs 함수를 만들어 재귀형식으로 풀고있었다

처음에는 이해가 잘 안됐지만 몇시간에 걸쳐 읽어보니 또 이해가 됐다

 

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    int k = Integer.parseInt(br.readLine());

    for (int q = 0; q < k; q++) {
      ans = 0;

      r = Integer.parseInt(br.readLine());
      arr = new int[r + 1];
      vis = new int[r + 1];
      end = new int[r + 1];
      st = new StringTokenizer(br.readLine());

      for (int j = 1; j <= r; j++) {
        arr[j] = Integer.parseInt(st.nextToken());
      }

      for(int i =1;i<=r;i++){
        if(end[i] == 0){
          dfs(i);
        }
      }
      System.out.println(r - ans);

    }
  }
}

일단 수를 입력받는 부분은 위와 같다(대부분의 배열과 변수는 dfs 함수와 함께 사용해야하므로 전역변수로 선언하였다.)

vis는 현재 사이클에서 방문했느냐를 의미하고, end는 이미 그 사람이 팀을 짰는지를 확인했느냐를 의미한다.

따로 필요한 이유는 전부 다 end 배열을 사용해서 탐색했을 경우, 이 방문이 이전 사이클에 대한 것인지, 지금 사이클에 대한 것인지를 구별할 수 없기 때문이다.

 

static void dfs(int cur){
  vis[cur] = 1;
  if(vis[arr[cur]] == 0){
    dfs(arr[cur]);
  }
  int next= arr[cur];

  if(end[next] == 0 && vis[next] == 1){
    int now = arr[next];
    int per = 1;
    while(next != now){
      per++;
      now = arr[now];
    }
    ans += per;
  }
  end[cur] = 1;
}

dfs 함수는 위와 같이 생겼다.

일단, 방문여부를 탐색한다. 만약 아직 방문하지 않았을 경우 연결된 다음 노드를 탐색한다.

만약 다음 노드가 end는 0이면서 vis는 1인 경우, 사이클에 포함된다는 뜻이다.

그럼 이 노드를 기준으로 사이클을 탐지하며 이 사이클 내부에 해당하는 노드의 수를 센다.

이렇게 하면 사이클에는 포함이 되지 않지만 사이클 어딘가에 연결되어있는 노드(팀이 될 수 없는 노드)는 걸러지게 된다.

 

전체코드

package org.example;
import java.util.*;
import java.io.*;
import java.math.*;


public class Main {

  static int r;
  static int[] vis;
  static int[] end;
  static int[] arr;
  static int ans = 0;

  static void dfs(int cur){
    vis[cur] = 1;
    if(vis[arr[cur]] == 0){
      dfs(arr[cur]);
    }
    int next= arr[cur];

    if(end[next] == 0 && vis[next] == 1){
      int now = arr[next];
      int per = 1;
      while(next != now){
        per++;
        now = arr[now];
      }
      ans += per;
    }
    end[cur] = 1;
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    int k = Integer.parseInt(br.readLine());

    for (int q = 0; q < k; q++) {
      ans = 0;

      r = Integer.parseInt(br.readLine());
      arr = new int[r + 1];
      vis = new int[r + 1];
      end = new int[r + 1];
      st = new StringTokenizer(br.readLine());

      for (int j = 1; j <= r; j++) {
        arr[j] = Integer.parseInt(st.nextToken());
      }

      for(int i =1;i<=r;i++){
        if(end[i] == 0){
          dfs(i);
        }
      }
      System.out.println(r - ans);

    }
  }
}

 

4시간이나 걸렸다... 너무 어려웠다

 

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