오늘 풀어볼 문제는 ⭐그래프 트리 분할 이란 문제다.
1. 문제요약
정점
개, 간선
개의 그래프가 주어진다.
각 정점은
부터
까지 번호가 매겨져 있고, 간선도 입력되는 순서대로
부터
까지 번호가 매겨져 있다.
그래프에서 원하는 만큼 간선을 삭제해, 서로 다른 크기의 트리 2개로 분할해보자!
입력
5 5 // 정점의 개수 , 간선의 개수 개
1 2
1 3
2 3
3 4
4 5
출력
3 2
1 2 3
1 2
4 5
5
- N1 N2
- 첫 번째 트리의 정점 개수 N1과 두 번째 트리의 정점 개수 N2
- N1 + N2 = N이고, N1 ≠ N2 여야 함
- N1개의 정점 번호 (공백으로 구분)
- 첫 번째 트리에 속하는 정점들
- N1 - 1개의 간선 번호 (공백으로 구분)
- 첫 번째 트리에 포함된 간선의 번호 (입력 순서 기준 1부터 M까지 매겨짐)
- N2개의 정점 번호
- 두 번째 트리에 속하는 정점들
- N2 - 1개의 간선 번호
- 두 번째 트리에 포함된 간선의 번호
2. 문제 접근법
그래프를 분할할 수 없는 경우를 올바르게 짚는다면 효율적으로 해결할 수 있다.
- 2개의 트리로 분할할 수 없는 경우
-> 주어지는 정점 개수가 1개
-> 진작에 3개 이상의 분할된 그래프가 주어짐 (간선으로 연결되지 않은 3개 이상의 그래프) - 다른 크기로 분할할 수 없는 경우
-> 주어지는 정점 개수가 2개
-> 처음에 탐색한 그래프 크기가 주어진 정점 개수의 절반
3. 코드
3.1 입력
public class Main {
private static class Edge {
int to, idx;
public Edge(int to, int idx) {
this.to = to;
this.idx = idx;
}
}
static int n, m; // 정점, 간선
static List<List<Edge>> graph;
static boolean[] visited; // 정점 방문 확인
static int dfsCount = 0; // dfs 횟수 확인 (입력된 그래프 개수 확인)
static List<Integer> edgePath; // DFS 간선 순서 확인
static List<Integer> nodePath; // DFS 정점 순서 확인
static StringBuilder stringBuilder = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");
n = Integer.parseInt(stringTokenizer.nextToken());
m = Integer.parseInt(stringTokenizer.nextToken());
// 정점이 2개 이하
if (n <= 2) {
System.out.println(-1);
return;
}
visited = new boolean[n + 1];
visited[0] = true; // 0번 안씀
graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
for (int i = 1; i <= m; i++) {
stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");
int u = Integer.parseInt(stringTokenizer.nextToken());
int v = Integer.parseInt(stringTokenizer.nextToken());
// 양방향
graph.get(u).add(new Edge(v, i));
graph.get(v).add(new Edge(u, i));
}3.2 dfs
1번부터 n번까지 정점에 대해 for 루프를 돌며, 아직 방문하지 않은 정점이 있으면 해당 정점부터 DFS를 수행하여 하나의 연결 컴포넌트(서브그래프)를 탐색한다.
이 과정을 통해 전체 그래프가 몇 개의 연결 컴포넌트로 이루어져 있는지 확인할 수 있다.
for (int i = 1; i <= n; i++) {
// 방문 확인
if (visited[i]) continue;
// 3개 이상의 그래프가 입력된 경우를 확인
if (dfsCount == 2) {
System.out.println(-1);
return;
}
visited[i] = true;
dfsCount++;
// DFS 전에 경로 초기화
edgePath = new ArrayList<>();
nodePath = new ArrayList<>();
nodePath.add(i);
dfs(i);
// 모든 정점을 한 번에 방문했다면?
// 즉, 그래프가 1개가 입력되었다면?
// 마지막으로 방문한 정점 하나만 자르면 됨
if (edgePath.size() == n - 1) {
calc();
break;
}
// 첫 DFS가 끝나면
// 그래프 분할을 짐작할 수 있다.
// 예외의 경우도 이전 조건 분기로 자연스레 처리된다.
if (dfsCount == 1) {
// 그래프가 같은 크기의 트리 2개로 분할된다면?
if (2 * nodePath.size() == n) {
System.out.println(-1);
return;
}
stringBuilder
.append(nodePath.size())
.append(" ")
.append(n - nodePath.size())
.append("\n");
}
// 정점 방문 순서 출력
for (int node : nodePath) {
stringBuilder.append(node).append(" ");
}
stringBuilder.append("\n");
// 간선 방문 순서 출력
for (int edge : edgePath) {
stringBuilder.append(edge).append(" ");
}
stringBuilder.append("\n");
}
System.out.println(stringBuilder);
}
3.3 calc()
그래프 전체가 하나의 트리로 연결된 경우, 마지막에 방문한 정점 하나만 떼어내어 두 개의 트리로 나누는 방식이다.
즉, 정점 N개와 간선 N-1개가 완전 연결된 상태에서 하나의 간선과 정점만 떼어내면 두 개의 트리가 된다.
// 모든 정점을 한 번에 방문했다면?
// 즉, 그래프가 1개가 입력되었다면?
// 마지막으로 방문한 정점 하나만 자르면 됨
private static void calc() {
stringBuilder.append(n - 1).append(" ").append(1);
stringBuilder.append("\n");
for (int i = 0; i < nodePath.size() - 1; i++) {
stringBuilder.append(nodePath.get(i)).append(" ");
}
stringBuilder.append("\n");
for (int i = 0; i < edgePath.size() - 1; i++) {
stringBuilder.append(edgePath.get(i)).append(" ");
}
stringBuilder.append("\n");
stringBuilder.append(nodePath.get(nodePath.size() - 1));
stringBuilder.append("\n");
}
3.4 dfs
흔한 dfs 함수다
// 정점과 간선 방문 순서를 기록하는
// 일반적인 DFS
private static void dfs(int nodeIdx) {
List<Edge> edges = graph.get(nodeIdx);
for (Edge edge : edges) {
if (visited[edge.to]) continue;
visited[edge.to] = true;
edgePath.add(edge.idx);
nodePath.add(edge.to);
dfs(edge.to);
}
}
}
