BaekJoon 4195 Java

BaekJoon

[BaekJoon] 4195번 친구 네트워크 (Java) 문제 풀이 [Gold 2]

문제 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 어떻게 풀 것인가? 문제를 읽어보자. ", 두 사람의 친구 네트워크에 몇 명이 있는지 구하는" 이라는 어절을 읽었을 때, 집합에 대한 개념과 이를 이용한 유니온-파인드 알고리즘을 떠올려서 문제를 풀었다. 하지만 시간초과가 발생했다. 왜 일까? 단순 유니온 - 파인드 알고리즘만을 이용한다면, 공통된 친구를 찾는 부분에서 시간초과가 발생했다. 그래서 HashMap을 이용하여 시간복잡도..

Tenacity_Dev
'BaekJoon 4195 Java' 태그의 글 목록