나의 일기들🌊
-
그래프(Graph)
[JAVA]트리 색칠하기(BOJ-1693 [그래프,DP])
📂문제 설명 n개의 정점으로 이루어진 트리가 있다. 이 트리의 각 정점을 색칠하려고 한다. 색칠을 할 때에는 1, 2, 3, …, n번 색깔 중에 하나로 색칠하여야 한다. 각 색깔을 사용하여 한 개의 정점을 색칠할 때마다 1, 2, …, n의 비용이 든다. 즉, i번 색깔로 한 개의 정점을 색칠하면 i만큼의 비용이 든다는 것이다. 또한 정점에 색칠을 할 때에, 주어진 트리 상에서 인접해 있는 서로 다른 두 정점은 서로 다른 색깔로 칠해져야 한다. 이를 만족하면서, 전체 정점들을 색칠하는데 드는 총 비용을 최소화 하려 한다. 최소 비용을 계산하는 프로그램을 작성하시오. 입력 첫째 줄에는 정점 및 색깔의 개수 n(1≤n≤100,000)이 주어진다. 다음 n-1개의 줄에는 각 줄에 두 개의 정수로 주어진 트리..
-
그래프(Graph)
[JAVA]트리의 독립집합(BOJ-2213[그래프,DP])
📂문제 설명 그래프 G(V, E)에서 정점의 부분 집합 S에 속한 모든 정점쌍이 서로 인접하지 않으면 (정점쌍을 잇는 에지가 없으면) S를 독립 집합(independent set)이라고 한다. 독립 집합의 크기는 정점에 가중치가 주어져 있지 않을 경우는 독립 집합에 속한 정점의 수를 말하고, 정점에 가중치가 주어져 있으면 독립 집합에 속한 정점의 가중치의 합으로 정의한다. 독립 집합이 공집합일 때 그 크기는 0이라고 하자. 크기가 최대인 독립 집합을 최대 독립 집합이라고 한다. 문제는 일반적인 그래프가 아니라 트리(연결되어 있고 사이클이 없는 그래프)와 각 정점의 가중치가 양의 정수로 주어져 있을 때, 최대 독립 집합을 구하는 것이다. 입력 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이..
-
그래프(Graph)
[JAVA]합리적인 이동경로(BOJ-2176[그래프,DP,다익스트라])
📂문제 설명 그래프의 한 정점 S에서 다른 한 정점 T로 이동하려 한다. 이동할 때 T에 가까워지며 이동하는 경우, 이를 합리적인 이동경로라 한다. 물론 이러한 경로는 최단경로가 아닐 수도 있다. 그래프가 주어졌을 때 가능한 합리적인 이동경로의 개수를 구하는 프로그램을 작성하시오. S=1, T=2 인 경우로 한다. 입력 첫째 줄에 정점의 개수 N(1X->B 라는 경로가 100의 값이고 A->B 경로값이 50이라고 하면 무조건 A->B로만 가야한다.(최단 거리) 문제 풀이 간선에 대한 정점과 길이 값을 Node값으로 하여 저장해준다. 이때 간선의 길이를 오름차순으로 자동 정렬하여 저장 할 수 있도록 한다. ArrayList로 트리를 만들어 주고 입력한 간선의 정보를 Node로 묶어서 값을 넣어준다. 초기의..
