[알고리즘 BFS & DFS 20] CHOOSENUMBER
문제 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래와 같이 표가 주어졌다고 하자. 1234567 3 1 1 5 5 4 6 이 경우에는 첫째 줄에서 1, 3, 5를 뽑는 것이 답이다. 첫째 줄의 1, 3, 5밑에는 각각 3, 1, 5가 있으며 두 집합은 일치한다. 이때 집합의 크기는 3이다. 만약 첫..
2019. 8. 12.
[알고리즘 BFS & DFS 1] CONNECTEDCOMP
문제 정점의 번호가 1부터 N까지 존재하는 그래프 G가 존재하고, 어떠한 정점 집합 S={i, j, k,..} 끼리는 서로 간선으로 연결되어있으며, 그 이외의 정점 집합(S`)과는 연결되어있지 않을때, 집합 S로 그려지는 그래프를 그래프 G의 연결요소(Connected Component)라고 합니다. 만약 정점 집합 S와 S`의 합집합이 G의 정점의 전체일 경우, 그래프 G의 연결요소의 개수는 2개입니다. 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 V과 간선의 개수 E이 주어진다. (1 ≤ V ≤ 1,000, 0 ≤ E ≤ V×(N-1)/2) 둘째 줄부터 E개의 줄에 간선의 양 끝점 v1와 v2가..
2019. 8. 12.