문제

친구 네트워크

풀이

이문제는 그래프 문제이다. 그리고 사이클이 있을수도 있으며 양방향 그래프이기 때문에 dfs나 bfs처럼 전후관계가 명확하지 않다. 입력받은 관계가 노드를 이어주기 때문에 해당간선을 이어주는 배열을 사용함으로써 해당 관계와 연결되어있는 노드가 몇개인지 셀수 있는 유니온 파인드를 이용해야 한다

// 노드 맵 (K: 사람, V: 인덱스)
static HashMap<String, Intger> nodes;

nodes 에는 관계가 알려지게 될때 저장하게 될 이름과 그 이름이 등장한 순서를 저장한다 예를들면 red blue 가 불려졌을때 red는 1, blue는 그 다음인 2를 입력하게 된다

// 네트워크에서 가지고 있는 노드 개수 (인덱스: 불려진 사람, 값: 연결된 노드의 개수) 
int[] network = new int[f * 2];
// 부모-자식 관계를 정의
int[] parent = new int[f * 2];
for (int i = 0; i < f * 2; i++) {
	network[i] = 1; // 현재 노드만 이어진것으로 
    parent[i] = i; // 자기 자신을 저장
}

두 사람이 불려졌을때 무조건 왼쪽 노드가 parent로 변경되면 되는 거다 만약에 red blue인경우에 parent[1] = 1이면 network[2] = 1 이 될것이다.

int index = 0;
for (int i = 0; i < f; i++) {
	..
    if (!nodes.containsKey(a)) {
    	nodes.put(a, index++);
    }
    if (!nodes.containsKey(b)) {
    	nodes.put(b, index++);
    }
}

그리고 이 노드를 HashMap nodes에 저장해준다, 값으로는 불려진 순서대로 들어가면 된다. 만약중복으로 불려질경우에는 이전에 불려졌던 값을 사용하기 위해서 containsKey를 적용하여 index가 늘어나지 않는다

private static int union(int a, int b) {
	// 부모노드가 무엇인지 구한다
	a = find(a);
    b = find(b);
    
    // 부모노드가 같지않은 경우에 이어준다
    if (a != b) {
    	// 부모를 입력해준다.
    	parent[b] = a;
        // b의 네트워크 개수를 더해준다
        network[a] += network[b];
    }
    
    // 부모 노드의 개수를 리턴한다.
    return network[a];
}

여기에서 parent[a] = b는 해주지않는다. 왜냐면 네트워크를 저장할때 마지막 노드가 a임을 알려주어야 find를 할때 부모노드를 명확하게 할수있기 때문이다. red blue 인경우 red가 blue의 부모가 된다 라는 뜻이다.(red는 red가 부모이다.)

// 부모노드를 구한다
private static int find(int a) {
	// 단말노드(마지막노드) 인경우
	if (parent[a] == a) {
    	return a; // 현재 노드의 값(nodes의 인덱스)을 출력한다
    }
    
    return parent[a] = find(parent[a]);
}

부모를 구할때도 마찬가지로 종료 조건은 단말노드일경우 이다. 만약에 parent[1] = 1 일때 이노드는 단말 노드임을 확인하게 되는데 1이라는 값은 red에 대한 인덱스를 출력한 것으로, blue가 가지는 부모도 1일 것이므로(parent[2] = 1 이라..) 네트워크가 가지는 인덱스의 부모를 판별할때 사용하게 되는것이다.

사실 문제를 처음 풀때를 생각하면 유니온 파인드에 대한 문제인가를 단번에 알수있냐 하면.. 그게 어려웠던것 같다. network가 여러개가 등장할때마다 그저 bfs나 dfs를 구현하려고 했는데....... 10만개가 테스트번 나오면 아마도 메모리 공간이 쉽지 않을수도 있을것 같기도..

전체 코드

전체 코드