[Java] 백준 4195번 친구 네트워크

 

https://www.acmicpc.net/problem/4195

4195번: 친구 네트워크

문제바로가기

 

---

 

1. 접근방법

 

친구 네트워크라는 단어 친구 사이가 된다 이런 단어의 느낌에서 서로소집합의 느낌이 많이 났다.

그래서 유니온 파인드 사용해서 1번 2번 친구를 연결 후 부모를 갱신 부모가 같은 개수를 세서 값을 출력하하면 되겠다. 

-> 정상적으로 값은 출력이 가능했다. 하지만 시간초과

-> 시간을 잡아먹은부분은 갱신을 해주고 부모 배열을 1~n까지 모두 확인하기 때문이라 생각함

 

기본 유니온 파인드 방식에서 따로 하위원소의 개수를 세어주는 배열을 만들고 유니온을 실행할때 마다 

합치는 그룹의 원소를 더해주는 방식을 사용하면 되겠다 라고 생각함

 

2. 실수

 

두 친구를 하나의 네트워크에 합칠때 무조건 같은 부모라고 생각해서

sum[parents[name.get(temp)]] 이런식으로 내부모의 원소개수를 출력해줬는데

Math.max(sum[parents[name.get(temp)]], sum[parents[name.get(comp)]] 처럼

같은 집합이지만 부모가 다를경우가 있어서 두 친구의 그룹중 더큰 값으로 출력해줘야 했다

 

3. 느낀점

 

서로서집합문제를 풀때는 그냥 알고있니? 알면 풀어 라는 문제만 풀어서 그런지 비효율적일지 생각해보지않았는데 부모를 바꾸거나 합칠때 굉장히 많은 시간이 필요하다는 부분을 알게되었고 초기 부모배열의 초기값을 뭘로 주는지 원소수의 배열을 주냐에 따라 효율부분을 개선할 수 있다는것을 알게 되었음.

 

 

4. 코드

 

import java.io.*;
import java.util.*;
public class boj4195 {
	static class Reader {
	      int bfs = 1 << 16;
	      byte[] buffer = new byte[bfs];
	      int bufferPos = 0, bufferState = 0;
	      DataInputStream dis = new DataInputStream(System.in);

	      public String readLine() throws IOException {
	         byte[] buf = new byte[bfs]; // line length
	         int cnt = 0, c;
	         while ((c = read()) != -1) {
	            if (c == '\n') {
	               if (cnt != 0) {
	                  break;
	               } else {
	                  continue;
	               }
	            }
	            buf[cnt++] = (byte) c;
	         }
	         return new String(buf, 0, cnt);
	      }

	      byte read() {
	         if (bufferPos == bufferState) {
	            try {
	               bufferState = dis.read(buffer, bufferPos = 0, bfs);
	            } catch (IOException e) {
	               e.printStackTrace();
	            }
	            if (bufferState == -1)
	               buffer[0] = -1;
	         }
	         return buffer[bufferPos++];
	      }

	      int nextInt() {
	         int rtn = 0;
	         byte c = read();
	         while (c <= ' ')
	            c = read();
	         boolean neg = (c == '-');
	         if (neg)
	            c = read();
	         do
	            rtn = rtn * 10 + c - '0';
	         while ((c = read()) >= '0' && c <= '9');
	         if (neg)
	            return -rtn;
	         return rtn;
	      }
	   }
	static int parents[],n,sum[];
	public static void main(String[] args) throws IOException {
		Reader in = new Reader();
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int tc = in.nextInt();
		StringTokenizer stz;
		StringBuilder sb = new StringBuilder();
		HashMap<String, Integer> name;
		for(int t=0;t<tc;t++) {
			n = in.nextInt();
			parents = new int[2*n+1];
			sum = new int[2*n+1];
			for(int i=1;i<2*n+1;i++) {
				parents[i]=i;
				sum[i] = 1;
			}
			name = new HashMap<>();
			int cnt = 1;
			String temp,comp;
			for(int i=0;i<n;i++) {
				int res=0;
				stz = new StringTokenizer(in.readLine());
				temp = stz.nextToken();
				if(!name.containsKey(temp)) {
					name.put(temp, cnt++);
				}
				comp = stz.nextToken();
				if(!name.containsKey(comp)) {
					name.put(comp, cnt++);
				}
				
				if(findset(name.get(temp))!=findset(name.get(comp))) {
					union(name.get(temp), name.get(comp));
				}
				sb.append(Math.max(sum[parents[name.get(temp)]], sum[parents[name.get(comp)]])).append("\n");
			}
			name.clear();
		}
		sb.setLength(sb.length()-1);
		bw.write(sb.toString());
		bw.flush();
	}
	public static int findset(int a) {
		if(a == parents[a]) return a;
		return parents[a] = findset(parents[a]); // 경로 압축
	}
	public static void union(int a,int b) {
		a = findset(a);
		b = findset(b);
		if(a==b) return;
		if(a<b) {
			sum[a] += sum[b];
			parents[b] = a;
		}
		else {
			sum[b] += sum[a];
			parents[a] = b;
		}
		return;
	}
}

 

 

 

어케 통과했누?