/ SWEA

SWEA_3289_서로소집합_JAVA

문제 : 서로소집합

SWEA문제는 로그인을 해야 열람할 수 있습니다.

링크 : SWEA_3289_서로소집합

접근 방식

서로소 집합의 개념을 배울 수 있는 문제이다. 서로소집합은 말 그대로 서로소인 집합, 즉 공통 원소가 없는 두 집합을 의미한다.

문제를 통해 합집합, Union과 집합 안에 특정 값이 포함되어 있는지 확인하는 findSet를 사용해볼 수 있다.

풀이 방법

이번 문제는 인접 리스트와 트리 두가지를 이용하여 풀었다. 인접 리스트로 서로소 집합을 구현할 때는 각 노드별로 집합의 대표 노드의 주소와 같은 집합의 다음 노드의 주소를 함께 가지고 있도록 구현해야 하는 부분에 주의해야 한다. 트리는 1차원 배열의 인덱스와 값을 이용해서 구현하였다.

문제 자체는 간단했다. Union과 FindSet을 구현한 후 각 명령어에 따라서 출력만 진행하면 된다.

먼저 Union 메서드이다. 2개의 노드를 인자값으로 받아 두 노드의 대표 노드가 같은 노드라면 union이 불가능하므로 false를 리턴한다. 만약 리턴되지 않았다면, a에 b를 연결하고 b에 연결되어있는 노드의 대표 노드 정보를 a의 대표노드로 바꿔준다.

findSet 메서드는, 값을 입력받아서 계속해서 재귀호출을 하며 상위 노드를 불러온다. 그 상위 노드가 주어진 값과 같아지면 해당 값을 리턴하도록 한다.

위 두 가지의 메서드는 코드를 보면 더 이해가 쉬울 듯 하다.

코드를 잘못 짠 건지, 인접리스트를 사용한 코드에서는 문제풀이시 시간초과가 일어났다.

소스 코드 : 인접 리스트 사용


import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class D4_1238_Contact {

	static class Node{
		int V;
		Node link;
		public Node(int v, Node link) {
			super();
			V = v;
			this.link = link;
		}

		@Override
		public String toString() {
			return "Node [V=" + V + ", link=" + link + "]";
		}


	}
	static int cnt;
	static ArrayList<Integer> ansNumbers;
	public static void main(String[] args) throws NumberFormatException, IOException {

		System.setIn(new FileInputStream("input_1238.txt"));

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		String str;
		int tc = 1;
		while((str = in.readLine()) != null) {

			String splitStr[] = str.split(" ");

			int N = Integer.parseInt(splitStr[0]);

			int V = Integer.parseInt(splitStr[1]);

			Node[] nodeList = new Node[N];

			str = in.readLine();

			splitStr = str.split(" ");
			//유향 그래프 생성
			for(int i=0,n=splitStr.length;i<n;i+=2) {

				int from = Integer.parseInt(splitStr[i]);
				int to = Integer.parseInt(splitStr[i+1]);

				nodeList[from] = new Node(to,nodeList[from]);

			}
			ansNumbers = new ArrayList<>();
//			for(Node is : nodeList) {
//				System.out.println(is);
//			}



			System.out.printf("#%d %d\n",tc++,bfs(V,nodeList));
		}

	}

	public static int bfs(int start, Node[] nodeList) {
		Queue<Integer> queue = new LinkedList<Integer>();

		boolean[] visited = new boolean[nodeList.length];

		// 노드의 깊이를 저장할 배열
		int[] depth = new int[nodeList.length];
		// 처음 시작하는 곳은 깊이가 1
		depth[start] = 1;
		queue.offer(start);
		visited[start] = true;
		while(!queue.isEmpty()) {
			int current = queue.poll();
			ansNumbers.add(current);
//			System.out.print(current+" ");
			// current 정점의 인접 정점 처리(단, 방문하지 않은 인접 정점만)
			for(Node temp=nodeList[current]; temp!=null;temp = temp.link) {
				if(!visited[temp.V]) {
					queue.offer(temp.V);
					visited[temp.V] = true;
					// 깊이 기록
					depth[temp.V] += depth[current]+1;
				}
			}
		}
		// 가장 깊은 깊이에 있는 노드 중 가장 큰 값 찾기
		int ans = 0;
		for(int i=0;i<nodeList.length;i++) {
			if(depth[i] >= depth[ans]) {
				ans = i;
			}
		}

		return ans;
	}

}

~~~java

## 소스 코드 : 트리 사용

~~~java

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


// 링크드로 해봤는데 개느리다 왤까
public class D4_3289_서로소집합 {

	static class Node{
		int zip;

		Node link;

		Node parent;

		public Node(int zip, Node link, Node parent) {
			super();
			this.zip = zip;
			this.link = link;
			this.parent = parent;
		}

	}

	public static void main(String[] args) throws IOException {

		System.setIn(new FileInputStream("input_3289.txt"));

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(in.readLine());

		for (int tc = 1; tc <= T; tc++) {

			StringTokenizer st = new StringTokenizer(in.readLine()," ");

			int N = Integer.parseInt(st.nextToken());

			int M = Integer.parseInt(st.nextToken());

			Node arr[] = new Node[N+1];

			for(int i=1;i<=N;i++) {
				arr[i] = new Node(i,null,arr[i]);
				arr[i].parent = arr[i];
			}

			StringBuilder sb = new StringBuilder();

			sb.append("#").append(tc).append(" ");

			for(int i=0;i<M;i++) {
				st = new StringTokenizer(in.readLine()," ");
				int command = Integer.parseInt(st.nextToken());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				if(command == 0) {
					union(arr[a],arr[b]);
				}else if(command == 1) {
					if(findSet(arr[a],arr[b])) {
						sb.append(1);
					}else {
						sb.append(0);
					}
				}
			}
			System.out.println(sb);
		}


	}

	static boolean union(Node a, Node b) {

		if(a.parent == b.parent) {
			return false;
		}

		a.link = b;

		for(Node k = b;k!=null;k=k.link) {
			k.parent = a.parent;
		}
		return true;

	}

	static boolean findSet(Node a, Node b) {
		if(a.parent == b.parent) {
			return true;
		}else {
			return false;
		}
	}
}