[문제 풀이] 백준 4195 친구 네트워크

//친구 네트워크 package ds2; import java.util.Scanner; public class pro_4195 { static Pair[] fn; static int fn_size; static int d[]; static class Pair{ //이름과 부모인덱스를 저장하는 객체 String name; //int id; int pid; Pair(String name, int pid){ this.name=name; //this.id=id; this.pid=pid; } } public static void main(String args[]){ Scanner sc = new Scanner(System.in); int N=sc.nextInt(); for(int i=0;i<N;i++){ int M=sc.nextInt(); fn=new Pair[M*2]; d=new int[M*2]; fn_size=0; for(int j=0;j<M;j++){ String str1, str2; str1=sc.next(); str2=sc.next(); int ppid=union(str1,str2); check(ppid); } } } static void init(String str){ //새 객체 생성 fn[fn_size]=new Pair(str,fn_size); d[fn_size]=0; fn_size++; } static int IsInfn(String str1) //이미 있는 객체인지 확인하는 메소드 { for(int i=0;i<fn_size;i++){ if(fn[i].name.equals(str1)) //배열에 이미 있는 객체면 return i; //그 객체의 인덱스 반환 } init(str1); //아니면 새 객체 생성하고 return fn_size-1; //그 인덱스 반환 } static int union(String str1, String str2){ int str1_id=IsInfn(str1); int str2_id=IsInfn(str2); str1_id=find(str1_id); str2_id=find(str2_id); if(d[str1_id]<d[str2_id]){ fn[str1_id].pid=str2_id; return str2_id; } else{ fn[str2_id].pid=str1_id; if(d[str1_id]==d[str2_id]) d[str1_id]++; return str1_id; } } static int find(int x){ //인덱스가 x인 객체가 속한 집합의 부모를 찾는 메소드 if(fn[x].pid==x) return x; else return fn[x].pid=find(fn[x].pid); } static void check(int ppid){ int count=0; for(int i=0;i<fn_size;i++){ if(fn[i].pid==ppid) count++; } System.out.println(count); } }

먼저 위와 같은 방법으로 풀었더니 시간초과가 났습니다..

그래서 hashmap을 이용해서 다시 풀었습니다.

import java.util.HashMap; import java.util.Scanner; public class pro_4195_5 { static int root[]; // 루트 저장하는 배열 static int cnt[]; // 친구네트워크 세는 배열 static int find(int x){ if(root[x]==x) return x; else return root[x]=find(root[x]); } static int merge(int p, int q){ p=find(p); q=find(q); if(p!=q){ //두개 부모가 같지 않으면 root[q]=p; //p를 루트로 정함 cnt[p]+=cnt[q]; //루트끼리 합치므로 cnt를 서로 더해준다 cnt[q]=1; //q는 단말노드가 되었으므로 cnt 값을 1로 함 } return cnt[p]; } public static void main(String args[]){ int T; Scanner sc= new Scanner(System.in); T=sc.nextInt(); for(int i=0;i<T;i++){ //테스트케이스 int N, idx1,idx2,num=0; N=sc.nextInt(); root=new int[N*2]; cnt=new int[N*2]; HashMap<String,Integer>index = new HashMap<String,Integer>(); //String과 그에 따른 index를 같이 묶어서 저장하기 위해 hashmap 사용 String str1, str2; for(int j=0;j<2*N;j++){ //root와 cnt 초기화 root[j]=j; cnt[j]=1; } for(int j=0;j<N;j++){ str1=sc.next(); str2=sc.next(); if(index.containsKey(str1)==false) index.put(str1, num++); //hashmap에 str1이라는 키가 없으면 맵에 키와 인덱스 값 추가하고, 인덱스 하나 증가시킴 idx1=index.get(str1); //맵의 이름(키)에 해당하는 인덱스 벨류 값을 idx1에 저장 if(index.containsKey(str2)==false) index.put(str2, num++); //hashmap에 str2라는 키가 없으면 맵에 키와 인덱스 값 추가하고, 인덱스 하나 증가시킴 idx2=index.get(str2); //맵의 이름(키)에 해당하는 인덱스 벨류 값을 idx2에 저장 int result=merge(idx1,idx2); //두개 merge System.out.println(result); } } } }