개발 일기

20250918 TreeSet(feat HashSet) , 그래프 본문

TIL

20250918 TreeSet(feat HashSet) , 그래프

종현종현 2025. 9. 18. 14:51

TreeSet

TreeSet은 Set 인터페이스를 구현한 클래스로써 객체를 중복해서 저장할 수 없고 저장 순서가 유지되지 않는다는 Set의 성질을 그대로 가지고 있다.

 

TreeSet은 이진탐색트리의 구조로 이루어져 있다. 이진 탐색 트리는 추가와 삭제에는 시간이 조금 걸리지만 정렬, 검색에 높은 성능을 보이는 자료구조이다.

 

TreeSet은 이진탐색트리 중에서도 성능을 향상시킨 레드-블랙 트리로 구현되어 있다.

 

직접 만들어보는 TreeSet 코드

public class MyTreeSet {
	
	static TreeNode root;
	
	public static void main(String[] args) {
		root = new TreeNode(13);
		insert(root, 8);
		insert(root, 17);
		insert(root, 15);
		insert(root, 1);
		insert(root, 25);
		insert(root, 11);
		insert(root, 22);
		insert(root, 27);
		insert(root, 6);

	static public TreeNode insert(TreeNode node, int value) {
		if (node == null) {
			return new TreeNode(value);
		}
		
		if (value < node.value) {
			node.left = insert(node.left, value);
		} else if (value > node.value) {
			node.right = insert(node.right, value);
		}
		
		return node;
	}
	
	static class TreeNode {
		int value;
		TreeNode left;
		TreeNode right;
		
		public TreeNode(int value) {
			super();
			this.value = value;
		}
	}
}

부모보다 작으면 왼쪽 자식이되고 크면 오른쪽 자식이 된다.

 

만약 편향 트리가 되면 O(log n)을 유지할 수 없고 O(n)이 되어버리기 때문에 균형을 맞추기 위한 Red-Black Tree라는 알고리즘으로 구현되어 있다.

 

HashSet과 속도 비교

HashSet은 해시 테이블을 기반으로 하며, 요소의 순서를 보장하지 않는다. 삽입, 삭제, 검색의 평균 시간 복잡도는 O(1)이다.

그러나 정렬하려면 별도의 작업이 필요하며, 이로 인해 성능 차이가 발생할 수 있다.

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.TreeSet;

public class SetPerformanceComparison {

	public static void main(String[] args) {
		int n = 100000;
		
		long startTime = System.nanoTime();
		TreeSet<Integer> treeSet = new TreeSet();
		
		for (int i = 0; i < n; i++) {
			treeSet.add((int)(Math.random() * n));
		} 
		
		long endTime = System.nanoTime();
		System.out.println("TreeSet 삽입 시간: " + (endTime - startTime)+ "ns");
		
		startTime = System.nanoTime();
		HashSet<Integer> hashSet = new HashSet();
		
		for (int i = 0; i < n; i++) {
			hashSet.add((int)(Math.random() * n));
		}
		
		List<Integer> hashList = new ArrayList(hashSet);
		Collections.sort(hashList);
		
		endTime = System.nanoTime();
		System.out.println("HashSet 삽입 시간: " + (endTime - startTime)+ "ns");
	
	}
}

 

HashSet의 경우 별도로 정렬하는 코드를 넣어 속도를 비교해보았다.

 

그래도 HashSet이 빠른 것을 볼 수 있다. HashSet을 쓰자.

 

그래프

그래프는 여러 개의 점(노드 또는 정점)들이 선으로 연결된 구조를 나타내는 수학적인 개념이다.

예시로는

소셜 네트워크: 사람(정점)과 사람 간의 친구 관계(간선)를 나타내는 그래프

도로망: 도로의 교차점(정점)과 도로(간선)를 표현하는 그래프

웹 페이지: 웹 페이지(정점)과 링크(간선) 간의 관계를 나타내는 그래프

등이 있다.

 

용어

정점(Vertex): 그래프의 노드 또는 점을 말한다.

간선(Edge): 정점 간의 연결. 부모-자식 개념이 없다.

가중치(Weight): 간선(엣지)에 할당된 값으로, 주로 두 노드(정점) 간의 관계의 강도, 비용, 거리 등을 나타낸다.

차수(Degree): 정점에 연결된 간선의 수를 말한다.

진입 차수: 방향 그래프에서 특정 정점으로 들어오는 간선의 수

진출 차수: 방향 그래프에서 특정 정점에서 나가는 간선의 수

경로(Path): 그래프의 두 정점 간에 존재하는 간선의 연속을 말한다.

사이클(Cycle): 시작 정점에서 출발하여 다시 시작 정점으로 돌아오는 경로를 말한다.. 트리와 가장 큰 차이

연결 그래프: 모든 정점이 서로 연결된 그래프

포화 그래프: V 개의 정점을 가지는그래프는 최대 V *(V–1)/ 2 간선이 가능 예> 4개정점이있는그래프의최대간선수는 6(=>4*3/2) 개

부분 그래프(Subgraph): 원래 그래프의 일부 정점과 간선으로 구성된 그래프

방향 그래프: 간선에 방향이 있는 그래프. 예를 들어, A → B는 A에서 B로 가는 방향을 의미

무방향 그래프: 간선에 방향이 없는 그래프. A와 B 간의 관계는 양방향으로 해석

 

인접행렬로 저장하는 코드

import java.util.Scanner;

public class AdjacencyMatrix {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int V = sc.nextInt();
		int E = sc.nextInt();
		
		int[][] arr = new int[V + 1][V + 1];
		
		for (int i = 0; i < E; i++) {
			int from = sc.nextInt();
			int to = sc.nextInt();
			
			arr[from][to] = arr[to][from] = 1;
			
		}
	}
}

V는 정점의 수를 입력 받고 E는 간선의 개수를 입력 받는다.

 

인접리스트로 저장하는 코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class AdjacencyList {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int V = sc.nextInt();
		int E = sc.nextInt();
		
		List<List<Integer>> list = new ArrayList(V + 1);
		
		for (int i = 0; i <= V; i++) {
			list.add(new ArrayList());
		}
		
		for (int i = 0; i < E; i++) {
			int from = sc.nextInt();
			int to = sc.nextInt();
			
			list.get(from).add(to);
			list.get(to).add(from);
		}
		
		System.out.println();
	}
}

위의 코드와 동일하다.

 

DFS로 그래프를 탐색하는 방법

 

DFS 그림 출처: https://sethuram52001.medium.com/data-structures-and-algorithms-undirected-graph-processing-491d4fdefad0

 

인접행렬 코드

import java.util.Scanner;

public class 백준_1260_DFS_인접행렬 {

	static int N, M, startNo;
	static StringBuilder sb = new StringBuilder(20);
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String[] info = sc.nextLine().split(" ");
		
		N = Integer.parseInt(info[0]);
		M = Integer.parseInt(info[1]);
		
		int startNo = Integer.parseInt(info[2]);
		
		int[][] arr = new int[N + 1][N + 1];
		
		for (int i = 0; i < M; i++) {
			String[] oneline = sc.nextLine().split(" ");
			int from = Integer.parseInt(oneline[0]);
			int to = Integer.parseInt(oneline[1]);
			
			arr[from][to] = arr[to][from] = 1;
		} // 입력 끝
		
		boolean[] visited = new boolean[N + 1];
		dfs(arr, visited, startNo);
		
		System.out.println(sb);
		sc.close();
	}

	static void dfs(int[][] arr, boolean[] visited, int curNode) {
		visited[curNode] = true;
		
		sb.append(curNode).append(" ");
		
		for (int i = 1; i <= N; i++) {
			if (!visited[i] && arr[curNode][i] != 0) {
				dfs(arr, visited, i);
			}
		}
	}
}

dfs는 재귀함수로 구현을 했고 각 노드에 방문했는지를 확인하면서 진행한다.

시작 노드에서 출발해 연결된 노드를 따라 깊게 들어가며 탐색하다가, 더 이상 방문할 수 있는 노드가 없으면 재귀적으로 위로 돌아와 다른 경로를 탐색한다.

 

인접리스트 코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class 백준_1260_DFS_인접리스트 {

	static List<List<Integer>> list;
	static boolean[] visited;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt();
		
		list = new ArrayList(V + 1);
		visited = new boolean[V + 1];
		
		for (int i = 0; i <= V; i++) {
			list.add(new ArrayList(V + 1));
		}
		
		int E = sc.nextInt();
		int startNo = sc.nextInt();
		
		for (int i = 0; i < E; i++) {
			int f = sc.nextInt();
			int t = sc.nextInt();
			list.get(f).add(t);
			list.get(t).add(f);
		}
		
		for (int i = 1; i <= V; i++) {
			Collections.sort(list.get(i));
		}
		
		dfs(startNo);
		System.out.println(sb);
		sc.close();
	}
	
	static void dfs(int curNode) {
		visited[curNode] = true;
		sb.append(curNode).append(" ");
		
		for (int to:list.get(curNode)) {
			if (!visited[to]) {
				dfs(to);
			}
		}
	}
}

이 코드는 그래프를 인접 그래프로 표현한 뒤, DFS를 재귀 함수로 표현한 것이다.

각 정점의 인접 노드들은 Collections.sort()를 통해 오름차순으로 모두 정렬해서, 탐색 시 작은 번호부터 방문하도록 했다.

 

시작 노드부터 현재 노드를 방문 처리하고 인접 리스트를 순회하면서 아직 방문하지 않은 노드가 있으면 재귀적으로 탐색한다.

 

BFS로 그래프를 탐색하는 법

출처: https://pages.cs.wisc.edu/~ariana/

 

인접 행렬 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BFS_인접행렬 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int V = sc.nextInt();
		int E = sc.nextInt();
		int startNode = sc.nextInt();
		
		int arr[][] = new int[V + 1][V + 1];
		boolean[] visited = new boolean[V + 1];
		
		for (int i = 0; i < E; i++) {
			int f = sc.nextInt();
			int t = sc.nextInt();
			
			arr[f][t] = arr[t][f] = 1;
		}
		
        // BFS 탐색 시작
		Queue<Integer> q = new LinkedList();
		q.offer(startNode);
		
		visited[startNode] = true;
		
		StringBuilder sb = new StringBuilder();
		
		while(!q.isEmpty()) {
			int cur = q.poll();
			
			sb.append(cur).append(" ");
			// 현재 정점에서 갈 수 있는 모든 후보지 탐색
			for (int i = 1; i <= V; i++) {
				if (!visited[i] && arr[cur][i] != 0) {
					q.offer(i);
					visited[i] = true;
				}
			}
		}
		
		System.out.println(sb.toString());
		sc.close();
	}
}

큐를 이용해 구현했다. 

시작 노드부터 갈 수 있는 모든 후보지를 탐색하고 차례대로 탐색을 진행한다. 직관적이고 DFS보다 이해하기 쉽다.

 

인접리스트 코드

public class 백준_1260_BFS_인접리스트 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt();
		int E = sc.nextInt();
		int startNode = sc.nextInt();
		
		List<List<Integer>> list = new ArrayList();
		for (int i = 0; i <= V; i++) {
			list.add(new ArrayList());
		}
		
		for (int i = 0; i < E; i++) {
			int f = sc.nextInt();
			int t = sc.nextInt();
			list.get(f).add(t);
			list.get(t).add(f);
		}
		
		boolean visited[] = new boolean[V + 1];
		
		Queue<Integer> q = new LinkedList();
		q.offer(startNode);
		visited[startNode] = true;
		
		StringBuilder sb = new StringBuilder();
		
		while(!q.isEmpty()) {
			int cur = q.poll();
			// 하고 싶은 일
			sb.append(cur).append(" ");
			
			for (int i:list.get(cur)) {
				if (!visited[i]) {
					q.offer(i);
					visited[i] = true;
				}
			}
		}
		
		System.out.println(sb);
		sc.close();
	}
}

 

그래프 응용 - 최단 경로

가중치가 없는 그래프에서 정점간의 최단 경로를 찾는 방법은 BFS가 제일 좋다. (ex. 바둑판 미로 찾기)

 

경로를 추적하기 위해 parent의 정보를 저장할 배열을 사용하는 경우

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class BFS {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int V = sc.nextInt();
		int E = sc.nextInt();
		
		List<List<Integer>> list = new ArrayList();
		
		for (int i = 0; i <= V; i++) {
			list.add(new ArrayList());
		}
		
		for (int i = 0; i < E; i++) {
			int f = sc.nextInt();
			int t = sc.nextInt();
			list.get(f).add(t);
			list.get(t).add(f);
		}
		
		int start = sc.nextInt();
		int goal = sc.nextInt();
		
		boolean[] visited = new boolean[V + 1];
		
		int[] parent = new int[V + 1];
		
		Queue<Integer> q = new LinkedList();
		q.offer(start);
		visited[start] = true;
		
		parent[start] = -1;
		
		boolean found = false;
		
		while(!q.isEmpty()) {
			int cur = q.poll();
			// 하고 싶은 일
			if (cur == goal) {
				found = true;
				break;
			}
			
			for (int i: list.get(cur)) {
				if (!visited[i]) {
					q.offer(i);
					visited[i] = true;
					
					parent[i] = cur;
				} 
			}
		}
		
		if (found) {
			StringBuilder sb = new StringBuilder();
			
			for (int at = goal; at != -1; at = parent[at]) {
				sb.append(at).append(" ");
			}
			
			System.out.println(sb.reverse().toString().trim());
		} else {
			System.out.println("no found");
		}
	}
}

말 그대로 parent를 기억해두었다가 경로를 역으로 추적해 다시 reverse()로 경로를 출력한다.

저작자표시 (새창열림)

'TIL' 카테고리의 다른 글

20250923 인증 강화 알고리즘  (0) 2025.09.23
20250919 BFS 숨바꼭질 문제, 다익스트라(Dijkstra)  (0) 2025.09.19
20250916 순열/조합/부분집합 알고리즘, 트리  (0) 2025.09.16
프론트-백 통신 기초: HttpSession과 REST API 공부하기  (0) 2025.09.15
20250915 정렬 알고리즘  (0) 2025.09.15
'TIL' Related Articles more
Comments