백준 실버II - 11725 트리의 부모 찾기

백준 실버II - 11725 트리의 부모 찾기 문제 풀이

 

문제 설명

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

 

문제의 자세한 내용은 해당 링크를 통해 확인 : 문제 링크

 

풀이 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // input : count
        int nodeCount = Integer.parseInt(br.readLine()) - 1;
        Map<Integer, List<Integer>> map = new HashMap<>(nodeCount);
        int[] pNodes = new int[nodeCount];

        // input : graph
        while(nodeCount-- > 0) {
            int[] inputIntegerArr = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::valueOf)
                    .sorted()
                    .toArray();
            int a = inputIntegerArr[0], b = inputIntegerArr[1];
            addMap(map, a, b);
            addMap(map, b, a);
        }

        // logic
        calcKey(map, pNodes, 1);

        // output
        Iterator<Integer> it = Arrays.stream(pNodes).iterator();
        while(it.hasNext()) {
            sb.append(it.next().toString());
            if(it.hasNext())
                sb.append("\n");
        }
        System.out.println(sb.toString());
    }

    private static void addMap(Map<Integer, List<Integer>> map, int key, int value) {
        if(map.containsKey(key))
            map.get(key).add(value);
        else {
            ArrayList<Integer> list = new ArrayList<>();
            list.add(value);
            map.put(key, list);
        }
    }

    private static void calcKey(Map<Integer, List<Integer>> map, int[] pNodes, int key) {
        for(Integer i : map.get(key)) {
            if(i == 1 || pNodes[i - 2] > 0) continue;
            pNodes[i - 2] = key;
            calcKey(map, pNodes, i);
        }
    }
}

 

문제 해결 전략

이라 쓰고 문제를 보고서 어떻게 풀면 될까?에 대한 생각을 정리한 항목

입력으로 주어지는 연결된 두 정점이 "A B" 이런 식으로 들어오게 되는데, 자연스럽게 두 정점의 연결 방향이 "A -> B"라고 생각하는 바람에 "어.. 트리가 이상하게 그려지는데?"라는 생각을 하며 시작부터 난항을 겪었던 문제

연결 방향과 상관없이 연결된 두 정점을 표현한다는 것을 깨닫고 풀이 시작

해당 문제는 루트가 항상 '1'로 고정되어 있기 때문에 1에서 이어지는 다음 노드들을 기준으로 쭉 찾아가며 부모 노드를 기록하면 될 것이라고 생각하고 진행

결국 부모와 인접한 노드부터 시작하여 깊게 들어가며 부모 노드를 기록하며 진행하는 방식이므로 DFS(깊이 우선 탐색) 방식이라고 볼 수 있다.

구하고자 하는 결과가 2번 노드부터 마지막 노드까지 순서대로 부모 노드를 출력하는 것이기 때문에 굳이 트리를 만들 필요 없이 각 노드 간 연결 정보만 있으면 된다고 생각하여 각 노드를 Key 값으로, 해당 노드에 연결된 노드들을 Value로 갖는 맵으로 저장하여 사용

노드 '1'에 연결된 노드들의 부모 노드를 '1'로 설정 후 해당 노드들에 연결된 노드들을 탐색하며 Key 값을 부모 노드로 설정하는 로직 수행 (Key - Value에서 Value의 부모 = Key 설정, 이후 Value를 Key 값으로 하는 Value 탐색이므로 재귀로 구현)

해당 로직 수행 시 연결된 노드가 '1' 이거나, 이미 연결된 노드에 부모 노드가 설정이 되었다면 패스하는 조건을 추가하여 이미 탐색된 노드는 더 이상 탐색하지 않도록 설정하여 구현

 

처음부터 위 로직으로 대강 감을 잡고 풀이를 시작했지만.. 이상하게 집중이 안 되어서 계속 뻘짓을 하며 구현이 막히는 문제가 발생하여 생각보다 매우 오랜 시간이 걸려서 푼 문제입니다.

어찌저찌 구현을 했지만 의식의 흐름대로 구현을 했더니 시간 초과로 인한 실패가 발생하여 좀 더 집중해서 리팩터링 한 위 코드로 통과를 하였습니다. 시간 초과로 실패한 코드는 접어두었습니다.

Key에 연결된 노드들을 전부 저장하는 방식이 아니라, 입력 받은 데이터만 저장해서 하려고 하다보니 Value의 탐색도 필요해지고 하다보니.. 꼬이고 꼬여서 시간복잡도가 하늘로 가버린 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int nodeCount = Integer.parseInt(br.readLine()) - 1;
        Map<Integer, List<Integer>> map = new HashMap<>(nodeCount);
        int[] pNodes = new int[nodeCount];

        while(nodeCount-- > 0) {
            int[] inputIntegerArr = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::valueOf)
                    .sorted()
                    .toArray();
            if(map.containsKey(inputIntegerArr[0]))
                map.get(inputIntegerArr[0]).add(inputIntegerArr[1]);
            else {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(inputIntegerArr[1]);
                map.put(inputIntegerArr[0], list);
            }
        }

        calcKey(pNodes, map, 1);
        Iterator<Integer> it = Arrays.stream(pNodes).iterator();
        while(it.hasNext()) {
            sb.append(it.next().toString());
            if(it.hasNext())
                sb.append("\n");
        }
        System.out.println(sb.toString());
    }

    private static void calcKey(int[] pNodes, Map<Integer, List<Integer>> map, int key) {
        if(!map.containsKey(key)) return;
        for(Integer value : map.get(key)) {
            int index = value - 2;
            if(pNodes[index] == 0)
                pNodes[index] = key;
            else continue;
            calcKey(pNodes, map, value);
            calcValue(pNodes, map, value);
        }
    }

    private static void calcValue(int[] pNodes, Map<Integer, List<Integer>> map, int value) {
        if(map.values().stream().noneMatch(list -> list.contains(value))) return;

        Set<Map.Entry<Integer, List<Integer>>> entries = map.entrySet().stream()
                .filter(entry -> (entry.getKey() != 1 && entry.getValue().contains(value)))
                .collect(Collectors.toSet());

        for(Map.Entry<Integer, List<Integer>> entry : entries) {
            int key = entry.getKey();
            int index = key - 2;
            if(pNodes[index] == 0)
                pNodes[index] = value;
            else continue;
            calcKey(pNodes, map, key);
        }
    }
}

---

코드를 업로드해 둔 깃 허브