프로그래머스_4195_친구네트워크

문제 링크

조건

•  t  : 테스트 케이스
•  F  : 네트워크 수, 100,000 이하 => 친구 수는 최대 F*2명

 

접근 방법

• 친구 별 인덱스 값 고정하기 위해 HashMap 활용
• Rank Union-Find => parent[node] <= 0 일 경우 루트노드, parent[node] > 0 일 경우 자식 노드
• 두 친구가 이미 같은 집합일 경우는 union 과정을 건너뛰어야 함! => 메모리초과!

 

솔루션

public class Main {
	static int F;
	static int[] parent;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		HashMap<String, Integer> map;
		
		int t = Integer.parseInt(br.readLine().trim());
		while(t-- > 0) {
			F = Integer.parseInt(br.readLine().trim());//네트워크 수
			map = new HashMap<String, Integer>();
			parent = new int[2*F+1];
			int idx = 1;
            
			for(int i = 0; i < F; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
				String s = st.nextToken();
				String e = st.nextToken();
				
				if(!map.containsKey(s)) {
					map.put(s, idx++);
				}
				if(!map.containsKey(e)) {
					map.put(e, idx++);
				}
				
				int sIdx = map.get(s);
				int eIdx = map.get(e);
				
				int ps = findSet(sIdx);
				int pe = findSet(eIdx);
                
				if(ps != pe) {
					parent[pe] += parent[ps] - 1;//루트노드(자식노드 개수 합침)
					parent[ps] = pe;//두 집합 합침
				}
				
				System.out.println(-parent[pe]+1);//자기자신 + 1
			}
		}
		
		
	}
	
	public static int findSet(int n) {
		if(parent[n] <= 0) {
			return n;
		}
		return parent[n] = findSet(parent[n]);//반복탐색 횟수 줄이기 위해 매번 값 갱신
	}

}

 

리뷰

• 처음에 두 친구가 이미 같은 집합일 경우 Union과정을 건너뛰지 않아서 메모리 초과 오류가 계속 남
• findSet 메소드에서 return parent[n] = findSet(parent[n]) 과정으로 똑같은 탐색을 반복하지 않기 위해 매번 값을 갱신해 줘야 함