[백준/자바] 7511번: 소셜 네트워킹 어플리케이션

문제

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

풀이

• 한 사람이 다른 사람의 페이지를 방문했을 때, 친구 관계 그래프에서 두 사람 사이의 경로를 보여주는 기능
  • 경로가 없는 경우에는 보여주지 않음
• 사람이 많아질수록 경로를 구하는 시간이 매우 느려지게 되었음
• 두 사람 사이의 경로가 없는 경우에 경로를 찾기 위해 너무 오랜시간 그래프를 탐색하기 때문
• 따라서, 두 사람 사이의 경로가 존재하는지 미리 구해보려고 함
• 주어지는 두 사람이 친구 관계 그래프상에서 경로가 존재하는지 안 하는지를 구하는 프로그램을 작성하시오.

경로 압축을 통해 두 정점이 주어졌을 경우, 경로가 존재하는지 판별하면 됩니다.

이는 주로, Union-Find나 Floyd-Warshall 알고리즘을 이용합니다.

여기서 N의 값이 최대 10^6이 나올 수 있기 때문에 플로이드 워셜 알고리즘은 통과되기 어려울 것입니다.
따라서 Union-Find 알고리즘을 사용해 풀어보겠습니다.

	private static void make() {
		p = new int[n];
		s = new int[n];
		
		for (int i = 0; i < n; i++) {
			p[i] = i;
			s[i] = 1;
		}
	}

• 유니온 파인드를 시작하기 전에, 부모 배열과 사이즈 배열을 초기화해 줍니다.

	private static int find(int x) {
		if (p[x] == x) return x;
		return p[x] = find(p[x]);
	}

• find() 메서드입니다.
• 만약 본인의 부모가 자기 자신일 경우 x를 리턴
• 아닐 경우 부모의 부모를 찾아 경로를 압축해 줍니다.

	private static boolean union(int a, int b) {
		int ra = find(a), rb = find(b); // 각자의 부모
		
		if (ra == rb) return false; // 부모가 같을 경우 return
		
        // rb를 ra의 밑으로 넣을 것이기 때문에
        // 크기가 역전된 상황이라면 swap
		if (s[ra] < s[rb]) {
			int t = ra;
			ra = rb;
			rb = t;
		}
		
        // rb의 부모를 ra로 설정(합집합)        
		p[rb] = ra;
		s[ra] += s[rb]; // ra 밑에 rb가 들어왔으므로 ra의 크기에 rb 크기만큼 증가
		return true;
	}

• union()
• 크기가 더 큰 집합 밑으로 넣어줍니다.

			for (int i = 0; i < k; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				union(a, b);
			}

• 메인 메서드에서 친구 관계가 주어질 때마다 서로 union 연산을 진행해 줍니다.

			m = Integer.parseInt(br.readLine());
			for (int i = 0; i < m; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				int u = Integer.parseInt(st.nextToken());
				int v = Integer.parseInt(st.nextToken());
				
				if (find(u) == find(v)) {
					sb.append(1);
				} else {
					sb.append(0);
				}
				
				sb.append('\n');
			}

• m개의 줄에 미리 구할 쌍이 주어졌을 때, 서로의 부모를 비교하여 같을 경우에는 연결되어 있다는 것이므로 1, 아니라면 0을 출력해 줍니다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int n, k, m;
	
	static int[] p, s;
	
	private static void make() {
		p = new int[n];
		s = new int[n];
		
		for (int i = 0; i < n; i++) {
			p[i] = i;
			s[i] = 1;
		}
	}
	
	private static int find(int x) {
		if (p[x] == x) return x;
		return p[x] = find(p[x]);
	}
	
	private static boolean union(int a, int b) {
		int ra = find(a), rb = find(b);
		
		if (ra == rb) return false;
		
		if (s[ra] < s[rb]) {
			int t = ra;
			ra = rb;
			rb = t;
		}
		
		p[rb] = ra;
		s[ra] += s[rb];
		return true;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= t; tc++) {
			
			n = Integer.parseInt(br.readLine());
			k = Integer.parseInt(br.readLine());
			
			make();
			
			for (int i = 0; i < k; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				union(a, b);
			}
			
			sb.append("Scenario ").append(tc).append(":").append('\n');
			
			m = Integer.parseInt(br.readLine());
			for (int i = 0; i < m; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				int u = Integer.parseInt(st.nextToken());
				int v = Integer.parseInt(st.nextToken());
				
				if (find(u) == find(v)) {
					sb.append(1);
				} else {
					sb.append(0);
				}
				
				sb.append('\n');
			}
			
			sb.append('\n');
		}
		
		System.out.println(sb.toString());
	}

}