백준 4803 트리 Java

백준 4803 트리 Java

728x90

solved.ac = 골드 4

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

1. 접근

문제를 풀기 전 시간 복잡도를 구하자!

V + E를 T만큼 반복하는데 T는 제시되어 있지 않다!

n과 m이 그리 크지 않으니 T도 상식적인 선 안에서 제시되니 일반적인 DFS로 접근해보자!

문제의 조건을 살펴보면

트리의 조건을 제시해주고 해당 조건을 만족하는 개수를

이 형식에 맞춰서 출력해주면 된다.

조건에서 제시된 트리의 기준은 정점이 n이라고 가정했을 때 간선이 n - 1을 충족하며 순환되지 않는 그래프이다.

즉, 간선의 수 == (간선 개수 - 1) * 2 (무방향 그래프로 양쪽 간선은 서로 연결되어 있으니 * 2로 확인한다)

예제의 첫 번째 케이스를 그림으로 살펴보면 (N = 6, M = 3)

여기서 주의할 점은 5번 노드나 6번 노드처럼 연결되어 있는 간선이 없더라도 5 -> 5, 6 -> 6도 카운트해야 한다.

매 케이스마다 위 그림처럼 트리의 개수를 세어 출력하자!

2. 풀이

변수 세팅

static int N, M, vertexCnt, edgeCnt, caseCnt; static ArrayList[] graph; static boolean[] visit; public static void main(String[] args) throws IOException { caseCnt = 0; while (true) { st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); if (N == 0 && M == 0) break; // 입력의 마지막은 0, 0 visit = new boolean[N + 1]; graph = new ArrayList[N + 1]; for (int i = 1; i <= N; i++) graph[i] = new ArrayList<>(); for (int i = 1; i <= M; i++) { st = new StringTokenizer(br.readLine()); int x = Integer.parseInt(st.nextToken()), y = Integer.parseInt(st.nextToken()); graph[x].add(y); graph[y].add(x); } solution(); } System.out.println(sb.toString()); }

DFS 호출 및 정답 출력

static void solution() { caseCnt++; int treeCnt = 0; for (int i = 1; i <= N; i++) { if (visit[i]) continue; // 방문여부 확인! vertexCnt = 0; edgeCnt = 0; DFS(i); // 트리의 조건 = 간선(edge)는 정점(vertex)의 갯수 - 1개 있어야 한다. // 무방향 그래프로 *2 하여 비교한다. if (edgeCnt == (vertexCnt - 1) * 2) treeCnt++; } sb.append("Case ").append(caseCnt).append(": "); if (treeCnt == 0) sb.append("No trees."); else if (treeCnt == 1) sb.append("There is one tree."); else sb.append("A forest of ").append(treeCnt).append(" trees."); sb.append('

'); }

DFS

static void DFS(int x) { vertexCnt++; // 정점 갯수 카운트! edgeCnt += graph[x].size(); // graph[x].size == 해당 정점에 연결 된 간선의 수 visit[x] = true; // 방문처리! for (int y : graph[x]) { if (visit[y]) continue; // 방문여부 확인! DFS(y); } }

3. 전체 코드

from http://dhbang.tistory.com/25 by ccl(A) rewrite - 2021-12-13 20:00:13