문제 유형
문제 접근
- 답
- 주어지는 정보
- 학생 수 최대 1000 (n)
- 학생 간의 인간관계 정보 최대 5000 (m)
- 후보
- 완전탐색
- 가능
- 학생의 수가 충분히 작음
- 완전탐색을 통한 n*n 연산을 시도했을 때, 시간 복잡도를 넘지 않음
- 유니온 파인드
- 적합
- 1번의 친구가 2번이고, 2번의 친구가 3번이라고 하자.
- 이 경우, 완전 탐색으로 1,2,3번의 친구 리스트를 전부 탐색하는 것도 된다.
- 하지만 유니온 파인드를 통해, 1, 2, 3번의 최종 친구를 정해놓으면 더 빨리 팀 개수를 구할 수 있다.
- 풀이(유니온 파인드)
- 목적
- 단계
- 자료구조
- List<Integer>[] FList;
- 친구 명단을 기록한다.
- a, b가 친구라면
- FList[a].add(b)
- FList[b].add(a)
- List<Integer>[] EList;
- 원수 명단을 기록한다.
- 원수의 원수는 친구이므로, 해당 경우는 FList에 등록한다.
- int[] unionList;
- 함수
- makeFriendByE()
- find(int target)
- union(int child, int parent)
- 부모가 없는 child가 parent를 가리키도록 한다.
import java.util.*;
import java.io.*;
public class Main {
static int n,m;
static List<Integer>[] FList;
static List<Integer>[] EList;
static int[] unionList;
static void makeFriendByE(){
int p, q;
for(int i = 1; i<=n; i++){
for(int j = 0; j<EList[i].size()-1; j++){
for(int k = j+1; k<EList[i].size(); k++){
p = EList[i].get(j);
q = EList[i].get(k);
FList[p].add(q);
FList[q].add(p);
}
}
}
}
static int find(int target){
if(unionList[target] == target){
return target;
}
return unionList[target] = find(unionList[target]);
}
static void union(int child, int parent){
child = find(child);
parent = find(parent);
if(child == unionList[child]){
unionList[child] = parent;
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
m = Integer.parseInt(st.nextToken());
FList = new ArrayList[n+1];
EList = new ArrayList[n+1];
unionList = new int[n+1];
for(int i = 1; i<=n; i++){
FList[i] = new ArrayList<>();
EList[i] = new ArrayList<>();
unionList[i] = i;
}
char ch;
int p,q;
for(int i = 1; i<=m; i++){
st = new StringTokenizer(br.readLine());
ch = st.nextToken().charAt(0);
p = Integer.parseInt(st.nextToken());
q = Integer.parseInt(st.nextToken());
if(ch == 'F'){
FList[p].add(q);
FList[q].add(p);
}
else{
EList[p].add(q);
EList[q].add(p);
}
}
makeFriendByE();
for(int i = 1; i<=n; i++){
for(int j = 0; j<FList[i].size(); j++){
int a = i;
int b = FList[i].get(j);
union(b,a);
}
}
int cnt = 0;
boolean[] visited = new boolean[n+1];
for(int i = 1; i<=n; i++){
int target = unionList[i];
if(visited[target] == true){
continue;
}
visited[target] = true;
cnt++;
}
System.out.println(cnt);
}
}
다른 풀이
- 시도 방법
- 풀이
- 친구 리스트를 전부 구한다
- 1, 2, 3번이 친구라고 할 시,
- 1, 2, 3번이 가지는 친구 리스트를 전부 뒤져서 팀을 형성한다.
import java.util.*;
import java.io.*;
public class Main {
static int n,m;
static List<Integer>[] FList;
static List<Integer>[] EList;
static void makeFriendByE(){
int p, q;
for(int i = 1; i<=n; i++){
for(int j = 0; j<EList[i].size()-1; j++){
for(int k = j+1; k<EList[i].size(); k++){
p = EList[i].get(j);
q = EList[i].get(k);
FList[p].add(q);
FList[q].add(p);
}
}
}
}
public static void makeTeam(int num, boolean[] visited){
if(visited[num] == true){
return;
}
visited[num] = true;
for(int i = 0; i<FList[num].size(); i++){
int target = FList[num].get(i);
makeTeam(target, visited);
}
}
public static void printFList(){
System.out.println("------printFList--------");
for(int i = 1; i<=n; i++){
System.out.print("num " + i + " : ");
for(int j = 0; j<FList[i].size(); j++){
System.out.print(FList[i].get(j) + " ");
}
System.out.println();
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
m = Integer.parseInt(st.nextToken());
FList = new ArrayList[n+1];
EList = new ArrayList[n+1];
for(int i = 1; i<=n; i++){
FList[i] = new ArrayList<>();
EList[i] = new ArrayList<>();
}
char ch;
int p,q;
for(int i = 1; i<=m; i++){
st = new StringTokenizer(br.readLine());
ch = st.nextToken().charAt(0);
p = Integer.parseInt(st.nextToken());
q = Integer.parseInt(st.nextToken());
if(ch == 'F'){
FList[p].add(q);
FList[q].add(p);
}
else{
EList[p].add(q);
EList[q].add(p);
}
}
makeFriendByE();
//printFList();
int cnt = 0;
boolean[] visited = new boolean[n+1];
for(int i = 1; i<=n; i++){
if(visited[i] == true){
continue;
}
cnt++;
makeTeam(i, visited);
}
System.out.println(cnt);
}
}