4195 친구 네트워크
문제
민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.
어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.
친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.
출력
친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.
예제 입력 1
2
3
Fred Barney
Barney Betty
Betty Wilma
3
Fred Barney
Betty Wilma
Barney Betty
예제 출력 1
2
3
4
2
2
4
나의 풀이
기존 풀었던 유니온 파인드는 숫자로 된 노드를 연결하는 문제였다
이번 문제는 문자로 된 노드들이 등장한다
기존 풀었던 방식으로 풀기 위해서는 Map이 필요하다고 생각했다
Key에 이름을, Value에는 자신의 노드를 저장한다
(처음에 이름은 변하지 않고, 노드 값을 Map 안에서 바꾸고자 했다)
Map에는 TreeMap, HashMap, LinkedHashMap이 있으며,
굳이굳이 순서가 맵 안에서는 필요 없다고 느껴서
사전 순으로 나열하는 TreeMap과, 입력 순서를 기억하는 LinkedHashMap까지 쓸 필요는 없어 보였다
HashMap을 사용해 입력받은 정보들을 저장했다
또한 static 변수로 대표 노드를 저장하는 parent 배열을 선언했다
배열의 크기가 문제였는데, 친구 관계 수 F만 주어지기 때문에, 친구의 수는 최대 2*F였다
어떻게 친구 네트워크를 카운트 할 수 있을까가 문제였다
정보를 저장하는 카운트 배열이 필요했다
정보를 저장할 변수들을 만들고 난 뒤,
입력받는 정보를 map 내에서 비교하여 없으면 새로운 노드 번호를 부여하여 put 해준다
그리고 union find를 실행한다
조금 다른 점은 union시 대표 노드가 다르다면,
지금까지 연결된 친구들을 대표 노드에 더해줘야 했다
이 정보를 저장하기 위해 count 배열을 생성했었다
풀이는 다음 코드와 같다
public class Main {
static HashMap<String, Integer> map;
static int[] parent; // 대표 노드 저장
static int[] count; // 친구 수 저장
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb= new StringBuilder();
int T = Integer.parseInt(br.readLine());
for(int tc = 1; tc <= T; tc++) {
int N = Integer.parseInt(br.readLine()); // 친구 수
map = new HashMap<>();
parent = new int[N * 2 + 1];
for(int i = 1; i <= N*2; i++) {
parent[i] = i;
}
count = new int[N * 2 + 1];
Arrays.fill(count, 1); // 네트워크에 자기는 기본으로 포함되므로, 1로 배열 초기화
int idx = 1;
for(int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
String a = st.nextToken();
String b = st.nextToken();
if(!map.containsKey(a)) {
map.put(a, idx++);
}
if(!map.containsKey(b)) {
map.put(b, idx++);
}
union(map.get(a), map.get(b)); // union 실행
int min = Math.min(map.get(a), map.get(b));
sb.append(count[find(min)]+"\n");
}
}
System.out.println(sb);
}
public static void union(int a, int b) {
a = find(parent[a]);
b = find(parent[b]);
if(a != b) {
parent[b] = a;
count[a] += count[b]; // 친구 네트워크 수 합치기
}
}
public static int find(int a) {
if(parent[a] == a) {
return a;
} else {
return parent[a] = find(parent[a]);
}
}
}궁금했던 점
유니온 파인드를 실행했을 때 대표 노드가 전부 수정될 줄 알았는데,
// parent 노드 최종
[0, 1, 1, 1, 3, 5, 6]이렇게 4번 Wilma의 노드가 1로 수정이 안됐었다
어떻게 해결할 수 있을까? 한참 고민을 했는데
System.out.println("Wilma: "+find(map.get("Wilma")));
System.out.println(Arrays.toString(parent));이렇게 find 함수를 마지막에 한 번 실행해 보았다
Wilma: 1
[0, 1, 1, 1, 1, 5, 6]find 함수가 실행되지 않아서 그랬던 것 같다
