백준 1889번: 선물 교환

문제 설명

• https://www.acmicpc.net/problem/1889
• 모두 선물을 2개만 받을 수 있게 만드는 경우의 수 중 길이가 가장 긴 경우를 구하는 문제입니다.

접근법

• 위상 정렬을 이용해 푸는 문제입니다.
  보통의 위상정렬은 진입차수가 0인 값부터 제거를 시작합니다.
  하지만 이 문제에서는 진입차수가 1인 경우도 절대 정답에 포함될 수 없습니다.(반드시 2개의 선물을 받아야 하기 때문)
• 진입차수가 1인 경우를 우리가 제거해야 하는가?에 대한 고민이 있었는데 아래와 같은 반례를 찾았습니다.

5
2 3
1 4
4 5
3 5
3 4

6
2 6
3 4
1 5
5 6
4 6
4 5

두 경우 모두 진입차수가 0인 경우는 없으며, 진입차수가 1인 경우를 제거했을 때 정답을 구할 수 있는 경우입니다. 그림으로 그려보면 이해하기 쉽습니다.

• 진입차수가 1인 경우를 포함하면 순환참조 문제가 발생합니다.

  // 처음 생각한 위상정렬 코드, 단순히 0값을 판단하던 곳을 0또는 1을 판단하게(<2)로 바꿔줬습니다.
  for (int i = 1; i <= N; i++) {
      if(inDegree[i] < 2) {
          pq.add(i);
      }
  }		
  
  while(!pq.isEmpty()) {
      int now = pq.poll();
      if(v[now]) continue;
      v[now] = true;
      for (int targetVal : graph.get(now)) {
          inDegree[targetVal]--;
          if(inDegree[targetVal] < 2) {
              pq.add(targetVal);
          }
      }
  }

  진입차수를 0인 경우만 고려했을 때는 a->b->c->a의 경우가 pq에 들어오지 못했습니다.
  하지만 진입차수가 1인 경우를 포함하면 위 경우가 pq에 들어오고 이때 무한루프에 빠질 수 있습니다.

  • 위 예시의 진입차수는 현재 [1,1,1]입니다. 여기서 a를 pq에 넣었다고 가정해 봅시다.
  • pq.poll()에서 a가 나왔습니다. a는 자신과 연결된 b의 진입차수를 1 줄입니다. b는 진입차수가 0이 되어 pq에 들어갑니다.
  • pq.poll()에서 b가 나왔습니다. b는 자신과 연결된 c의 진입차수를 1 줄입니다. c는 진입차수가 0이 되어 pq에 들어갑니다.
  • pq.poll()에서 c가 나왔습니다. c는 자신과 연결된 a의 진입차수를 1 줄입니다. a는 진입차수가 0이 되어 pq에 들어갑니다.
  • pq.poll()에서 a가 나왔습니다. a는 자신과 연결된 b의 진입차수를 1 줄입니다. 음수의 진입차수를 가질 수 없게 막아두더라도 b의 진입차수는 2보다 작은 값이 되어 또다시 pq에 들어갑니다.
  • 반복됩니다.
    -> 방문배열을 표시해 문제를 해결했습니다.

정답

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		HashMap<Integer,int[]> graph = new HashMap<Integer,int[]>();
		int[] inDegree = new int[N+1];
		boolean[] v = new boolean[N+1];
		for (int i = 1; i <= N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			inDegree[a]++;
			inDegree[b]++;
			graph.put(i, new int[] {a,b});
		}
		
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
		
		for (int i = 1; i <= N; i++) {
			if(inDegree[i] < 2) {
				pq.add(i);
			}
		}		
		
		while(!pq.isEmpty()) {
			int now = pq.poll();
			if(v[now]) continue;
			v[now] = true;
			for (int targetVal : graph.get(now)) {
				inDegree[targetVal]--;
				if(inDegree[targetVal] < 2) { 
					pq.add(targetVal);
				}
			}
		}		

		StringBuilder sb = new StringBuilder();
		int cnt = 0;
		for (int i = 1; i <= N; i++) {
			if(inDegree[i] == 2) {
				cnt++;
				sb.append(i+" ");
			}
		}
		System.out.println(cnt);
		System.out.println(sb.toString());

	}

}