백준 11725 트리의 부모 찾기 JAVA

solved.ac = 실버 2

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

11725번: 트리의 부모 찾기

 

1. 접근

 

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

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

 

 

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

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

 

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

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

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

 

2. 풀이

 

변수 세팅

static int N;
static ArrayList<Integer>[] 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('\n');
    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. 전체코드