[백준] 2668번 - 숫자 고르기

문제 >

세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래와 같이 표가 주어졌다고 하자.

 

이 경우에는 첫째 줄에서 1, 3, 5를 뽑는 것이 답이다. 첫째 줄의 1, 3, 5밑에는 각각 3, 1, 5가 있으며 두 집합은 일치한다. 이때 집합의 크기는 3이다. 만약 첫째 줄에서 1과 3을 뽑으면, 이들 바로 밑에는 정수 3과 1이 있으므로 두 집합이 일치한다. 그러나, 이 경우에 뽑힌 정수의 개수는 최대가 아니므로 답이 될 수 없다.

 

입력 >

첫째 줄에는 N(1≤N≤100)을 나타내는 정수 하나가 주어진다. 그 다음 줄부터는 표의 둘째 줄에 들어가는 정수들이 순서대로 한 줄에 하나씩 입력된다.

 

출력 >

첫째 줄에 뽑힌 정수들의 개수를 출력하고, 그 다음 줄부터는 뽑힌 정수들을 작은 수부터 큰 수의 순서로 한 줄에 하나씩 출력한다.

 

해결방법 > 

깊이 우선 탐색(DFS) 알고리즘으로 문제 해결

 

예제에 있는 데이터로 그래프를 그려보면 경로가 cycle을 가졌을 때, 두 집합에 모두 포함되게 된다.

즉, 입력받은 데이터가 방향이 있는 그래프의 간선에 대한 정보로 보고, 이 그래프에서 cycle을 가지는 경로의 정점을 찾는 문제이다.

 

dfs로 cycle을 가지는 경로에 포함되는 정점을 모두 찾아준다.

 

[JAVA]

package baekjoon;

import java.util.*;

public class BOJ_2668 { 
	static int[][] map;
	static boolean[] visit;
	static int v;
	static int cnt = 0;
	static ArrayList <Integer> list = new ArrayList<>();
	
	public static void dfs(int x, int y) {
		if(x == y) {
			list.add(x);
			cnt++;
		}
		visit[x] = true;
		
		for(int i = 1; i <= v; i++) {
			if(map[x][i] == 1 && visit[i] == false) {
				dfs(i, y);
			}
			visit[i] = false;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		v = sc.nextInt();
		map = new int[v+1][v+1];
		visit = new boolean[v+1];
		
		for(int i = 1; i <= v; i++) {
			int x = sc.nextInt();
			map[i][x] = 1;
		}
		
		for(int i = 1; i <= v; i++) {
			for(int j = 1; j <= v; j++) {
				if(map[i][j] == 1 && visit[j] == false) {
					dfs(j, i);
				}
			}
		}
		System.out.println(cnt);
		for(int i = 0; i < list.size(); i++) {
			System.out.println(list.get(i));
		}
	}
}

 

문제링크 >

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

2668번: 숫자고르기