문제 출처: jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=731&sca=2080
문제 조건
예) 크기가 7인 배열이
1 2 3 4 5 6 7
3 1 1 5 5 4 6
으로 값이 들어있다면, 인덱스 집합과 값 집합이 가장 크게 일치하려면 1, 3, 5를 뽑으면 된다. 가장 큰 크기는 3이다.
1 2 3 4 5 6 7
3 1 5 5 6 5 6
인 경우에는 1, 3, 5, 6이 되겠다. 크기는 4이다.
풀이 방법
- 배열의 인덱스와 값을 node로 생각하여 연결고리가 있는 그래프인지 확인하면된다.
- 확인을 위해서는 dfs를 통해 노드를 계속 타고 들어가서 결국 처음시작한 노드와 끝나는 노드가 일치하는지 확인하면 된다.
- set은 이미 완성된 그래프의 노드(요소)인지 확인하는 것이다. 그래프가 형성되어 있으면 해당 노드번호들을 set에 담는다.
- checkArr은 연결된 그래프를 찾기위해 활용되는 불린 배열이다.
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class 숫자고르기_1459 {
private static int count;
private static HashMap<Integer, Integer> map;
private static boolean[] checkArr;
private static int firstInt;
private static HashSet<Integer> set;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
map = new HashMap<Integer, Integer>();
for (int i = 1; i < N + 1; i++) {
map.put(i, Integer.parseInt(br.readLine()));
}
set = new HashSet<Integer>();
checkArr = new boolean[N + 1];
count = 0;
Arrays.fill(checkArr, false);
for (int i = 1; i < N + 1; i++) {
if (!set.contains(i)) { // 완성된 그래프의 노드가 아닌경우
checkArr[i] = true;
firstInt = i;
dfs(i);
Arrays.fill(checkArr, false);
}
}
System.out.println(count);
ArrayList<Integer> answerArr = new ArrayList<Integer>(set);
Collections.sort(answerArr);
answerArr.forEach(i -> System.out.println(i));
}
static void dfs(int key) {
if (firstInt == map.get(key)) { // 다음에 방문할 value가 처음에 찾던 key값이랑 동일하면 그래프 형성
for (int i = 1; i < checkArr.length; i++) {
if (checkArr[i]) {
count++;
set.add(i);
}
}
return;
}
if (checkArr[map.get(key)]) { // 다음에 방문할 곳이 방문했던 곳이면 return
return;
}
checkArr[map.get(key)] = true;
dfs(map.get(key));
}
}