[BOJ] 백준 11725번 트리의 부모 찾기 - JAVA 자바 풀이

접근법

트리는 그래프의 일종입니다. 문제에서 입력으로 주어지는 노드의 연결 정보는 그래프의 간선 정보나 다름 없습니다.

간선 정보로 그래프를 구성한 뒤 트리의 루트인 1번 정점에서 부터 그래프 탐색을 하면 됩니다.

 

그래프 초기화

입력으로 주어진 간선 정보를 토대로 그래프를 초기화 하는 코드입니다.

각 정점에 연결된 인접 정점들을 표기하기 위해 Map<Integer, LinkedList<Integer>> 자료구조를 사용했습니다.

static Map<Integer, LinkedList<Integer>> tree = new HashMap<>();

public static void initTree(int v, int w) {
    if(!tree.containsKey(v)) { // 정점 v를 최초로 입력 받았을 경우
        LinkedList<Integer> list = new LinkedList<>();
        list.add(w);
        tree.put(v, list);
    } else { // 정점 v가 이미 Map에 존재할 경우
        tree.get(v).add(w);
    }
}

 

DFS 그래프 탐색

n번 노드에 방문을 했는지 아닌지 탐색 여부는 int[] 배열 자료구조를 사용했습니다.

n번 노드의 부모를 myParent 배열에 저장함과 동시에, 해당 노드의 탐색 여부를 알 수 있습니다.

static int[] myParent;

public static void dfs(int parent) {
    for(int children : tree.get(parent))
        if(myParent[children] == 0) { // 아직 노드를 탐색하지 않은 경우
            myParent[children] = parent;
            dfs(children);
        }
}

 

Java 코드

public class Main {
    static Map<Integer, LinkedList<Integer>> tree = new HashMap<>();
    static int[] myParent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        myParent = new int[N+1];
        myParent[1] = -1; // 루트의 부모는 없으므로 -1

        for(int i=1; i<=N-1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            initTree(v, w);
            initTree(w, v);
        }

        dfs(1); // 트리의 루트인 1번 정점부터 탐색

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i=2; i<=N; i++)
            bw.write(myParent[i] + "\n");

        bw.flush();
        bw.close();
    }

    public static void initTree(int v, int w) {
        if(!tree.containsKey(v)) { // 최초로 v를 입력 받았을 경우
            LinkedList<Integer> list = new LinkedList<>();
            list.add(w);
            tree.put(v, list);
        } else { // 이미 v 정점을 입력 받은 경우
            tree.get(v).add(w);
        }
    }

    public static void dfs(int parent) {
        for(int children : tree.get(parent))
            if(myParent[children] == 0) { // 아직 노드에 방문하지 않았을 경우
                myParent[children] = parent;
                dfs(children);
            }
    }
}

 

문제 링크

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