https://www.acmicpc.net/problem/2668
문제를 잘못 이해하고 있었다
저 부분을 간과해버려서 한참 헤맸다;;
첫째줄에서 무작위로 선택하다 1,3,5 선택하면 밑에줄의 3,1,5 집합과 일치하게 된다
이런경우들이 많을 텐데 그중에서 집합의 원소개수가 가장 많은 경우를 찾는것이다
초등부 문제인데 문제 이해하는것도 힘드네;;
dfs 완전탐색에서
이런 방식으로 뻗어나가게 탐색하는 dfs 함수를 짜면되지 않을까 생각해본다..
밑의 그림처럼
그리고 각 조합마다(원소개수: 1~N개) 하나의 원소를 정점으로 여기고 서로 연결되있는지 확인해서 맞다면 원소개수를 저장.
위의 과정을 반복하면서 원소개수가 크면 갱신하도록 하면 되지 않을까 생각하고 코드작업을 시작!
근데 뭔가 이상하다 엣지가 중복되있다. 1,3 3,1 같은경우가 그렇다
처음부터 다시 고민했다 엣지중복있는경우를 피하고 구현하면 되는건가? 아니다
애초에 정점이 서로 연결되있으면 원소개수 저장한다고 하는생각이 잘못되었다
정점들이 연결되어있다고 해서
윗줄의 숫자와 아랫줄의 숫자가 둘다 있다고 보장할 수 없다
그래서 풀이를 찾아보게 되었다
그리고 깨달음을 얻었다
어떤숫자를 탐색해서 다시 그 숫자로 돌아올 수 있는가? 가 핵심이다..
1, 3, 5 숫자는 탐색해서 자기자신으로 돌아올 수 있다. 이걸 실전에서도 발견할 수 있어야 하는데 흐미;;
이것이 초등부를 위한 문제란 말인가;;
이것을 자료구조로 어떻게 표현하지 생각해봤는데 괜히 어렵게 생각하고 있었다
ArrayList 로 이차원배열로 표현하면된다
그냥 샘플 문제대로
1 3
2 1
3 1
4 5
5 5
6 4
7 6
넣으면된다 생각해보니 ArrayList 가 필요없겠다 그냥 일차원 배열로 하면된다
너비탐색으로 풀었다..
시간복잡도는 N*N
import java.io.*;
import java.util.*;
public class Main
{
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] graph = new int[N+1];
for(int i = 1; i < N+1; ++i)
{
graph[i] = Integer.parseInt(br.readLine());
}
StringBuilder ans = new StringBuilder();
int count = 0;
for(int i = 1; i < N+1; ++i)
{
if(bfs(i, graph))
{
count++;
ans.append(i+"\n");
}
}
System.out.println(count);
System.out.println(ans);
}
private static boolean bfs(int start, int[] graph)
{
boolean[] visit = new boolean[graph.length];
Queue<Integer> que = new LinkedList<>();
que.offer(start);
visit[start] = true;
while(que.isEmpty() == false)
{
int cur = que.poll();
int adj = graph[cur];
if(adj == start)
return true;
if(visit[adj] == false)
{
visit[adj] = true;
que.offer(adj);
}
}
return false;
}
}