백준 11725 트리의 부모 찾기 JAVA

백준 11725 트리의 부모 찾기 JAVA

728x90

solved.ac = 실버 2

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

1. 접근

문제를 풀기 전 항상 시간 복잡도를 생각하자!

그래프 탐색에서의 시간 복잡도는 인접 행렬 = V², 인접 리스트 = V + E 이며 이번 문제 포함해 대부분의 문제는 인접 리스트로 접근하니 100,000 + 99,999 = 199,999로 시간 여유는 충분하다!

문제의 조건은 루트를 제외한 각 노드의 부모를 출력하는 것이다.

문제의 예제를 그림으로 그려서 접근해보자.

글로만은 이해가 어려우니 그림을 보며 이해해보자!

탐색을 진행하며 각 정점의 부모가 누구지? 로 접근하기 보다는 각 정점은 누구의 부모지? 로 접근하면 이해가 편하다.

즉, 재귀적으로 DFS를 호출할 때, 연결되어 있는 다음 정점의 번호와 현재 노드의 번호를 같이 넘겨 다음 노드와 연결되어 있는 정점 중 현재 노드를 제외한 값이 부모가 된다.

2. 풀이

변수 세팅

static int N; static ArrayList[] graph; static int[] parents; public static void main(String[] args) throws IOException { N = Integer.parseInt(br.readLine()); parents = new int[N + 1]; // 부모를 저장할 배열, 각 인덱스의 값이 부모다. graph = new ArrayList[N + 1]; for (int i = 1; i <= N; i++) graph[i] = new ArrayList<>(); for (int i = 1; i < N; 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(); }

DFS 호출 및 정답 출력

static void solution() { DFS(1, -1); //0과 1은 비어있으니 두 번째 인덱스부터 출력하자! for (int i = 2; i <= N; i++) sb.append(parents[i]).append('

'); System.out.println(sb.toString()); }

DFS

// x = 다음 노드, parent = 부모 노드 static void DFS(int x, int parent) { for (int y : graph[x]) { // x와 연결된 간선을 살펴보자! if (y == parent) continue; // 부모 노드는 제외한다! parents[y] = x; // x는 y의 부모다! DFS(y, x); } }

3. 전체코드

from http://dhbang.tistory.com/24 by ccl(A) rewrite - 2021-12-13 19:00:37