(4195) 친구 네트워크

생성일: 2023년 9월 30일 오후 1:45

🌍TISTORY

문제 🌐

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.

어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 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

접근 방법

Union Find라는 것을 알게 되어 사용해 보려고 했다. 다만, 이전에는 인덱스를 사용해서 구현해서 크게 헷갈리지 않았지만… String으로 구현하려다 보니 조금 헷갈렸다.

입력이 들어올 때, 두 명의 이름이 들어오는데, 무조건 자식 - 부모 순서대로 생각하기로 내 마음대로 규칙을 정했다.

  1. 친구 관계를 나타내는 <String, String> 맵과 무리에 속한 사람들 숫자를 나타내는 <String, Integer> 맵 두 개를 만들었다.
  2. 처음 받아왔을 때, 두 명 모두 자기 자신을 부모로 갖는 원소를 하나씩 생성한다. 여기서 아주 좋은 메소드를 알았다!!
				friends.putIfAbsent(person1, person1);
				friends.putIfAbsent(person2, person2);

key에 해당하는 메소드가 없다면 넣는 것이다. 이렇게 하면 사람 두 명이 존재하는지, 존재하지 않는지 경우의 수를 분기하지 않아도 된다. 심심할 때 클래스가 정의된 코드를 보는 것도 방법이다….

				// 무리에 속한 사람들 수를 초기화하는 맵
				cnt.putIfAbsent(person1, 1);
				cnt.putIfAbsent(person2, 1);

사람을 초기화하는 것도 같다.

				// person의 부모 찾고
				String parent1 = find(person1);
				String parent2 = find(person2);

				// 합친다 .
				union(parent1, parent2);

				System.out.println(cnt.get(parent2));

부모를 찾아 부모에 해당하는 사람들을 합친다. 왜냐하면 person1, person2가 같은 무리에 속해야 하기 때문에 같은 부모를 공유해야 한다.

관계가 주어졌을 때 매번 결과를 출력하라 했으므로 인원수를 출력한다.

집합 메소드

	static String find(String person) {
		if (!person.equals(friends.get(person))) {
			friends.put(person, find(friends.get(person)));
		}
		return friends.get(person);
	}

	static void union(String person1, String person2) {
		if (person1.equals(person2)) return;
		else {
			friends.put(person1, person2);
			// 1번 사람 무리 숫자 + 2번 사람 무리 숫자
			cnt.put(person2, cnt.get(person2)+cnt.get(person1));
		}
	}

Full Solution

import java.util.HashMap;
import java.util.Scanner;

public class Main {
	static HashMap<String, String> friends;
	static HashMap<String, Integer> cnt;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int test_case=1; test_case<=T; test_case++) {
			int network = sc.nextInt();
			friends = new HashMap<>();
			cnt = new HashMap<>();

			// 관계를 맵에 넣어주기
			// 키: 사람, 값: 부모
			for (int i=0; i<network; i++) {
				String person1 = sc.next();
				String person2 = sc.next();

				// 좋은 메서드를 알았습니다..
				// 일단 본인의 부모를 본인으로 설정하기
				friends.putIfAbsent(person1, person1);
				friends.putIfAbsent(person2, person2);

				// 무리에 속한 사람들 수를 초기화하는 맵
				cnt.putIfAbsent(person1, 1);
				cnt.putIfAbsent(person2, 1);

				// person의 부모 찾고
				String parent1 = find(person1);
				String parent2 = find(person2);

				// 합친다 .
				union(parent1, parent2);

				System.out.println(cnt.get(parent2));

			}


		}
	}


	static String find(String person) {
		if (!person.equals(friends.get(person))) {
			friends.put(person, find(friends.get(person)));
		}
		return friends.get(person);
	}

	static void union(String person1, String person2) {
		if (person1.equals(person2)) return;
		else {
			friends.put(person1, person2);
			// 1번 사람 무리 숫자 + 2번 사람 무리 숫자
			cnt.put(person2, cnt.get(person2)+cnt.get(person1));
		}
	}
}