[백준 - 11725] 트리의 부모 찾기 - Java

문제 설명

 

11725번: 트리의 부모 찾기

 

접근 방법

해당 문제는 DFS(깊이 우선 탐색)를 통해 해결할 수 있었습니다.

 

이 문제를 풀기 전까지만 해도 깊이 우선 탐색하면 주로 인접 행렬 방식으로 접근했었습니다. 인접 행렬 방식은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식으로 연결이 되지 않은 노드 정보들까지도 배열 상에 포함되어 있다고 볼 수 있습니다. 이러한 인접 행렬 방식의 단점은 메모리가 불필요하게 낭비된다는 점입니다. 앞서 언급했듯이 연결되지 않은 노드들의 정보들도 포함되기 때문입니다.

 

해당 문제에서는 노드의 개수 N이 최대 10만개로, 모든 노드들의 정보를 2차원 배열로 나타내면 기본형 타입 중 크기가 제일 작은 boolean형으로 포함하여도 100억(10만 * 10만)바이트에 달하게 되는데, 해당 문제에서의 메모리 제한은 256MB(약 2억7천만바이트)로 턱없이 부족한 수치입니다.

 

따라서 해당 문제는 인접 행렬 방식이 아닌 '인접 리스트 방식'으로 접근해야합니다. 인접 리스트 방식은 연결 리스트 또는 2차원 리스트를 이용하여 연결된 노드에 대한 정보들만 저장하는 방식인데, 비록 인접 행렬 방식 대비 특정 두 노드간 연결 정보를 탐색하는데에는 시간이 다소 소요되지만 메모리가 절약된다는 장점이 있습니다.

 

우선 인접 리스트 방식 구현을 위해 2차원 리스트를 선언해주었습니다. 이후에 입력되는 노드간 연결 정보를 다음과 같이 해당 리스트에 입력해주도록 합니다.

 

        Map<Integer, Integer> parentByNode = new HashMap<>();

        StringTokenizer st;
        int nodeData1, nodeData2;
        for (int i = 1; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            nodeData1 = Integer.parseInt(st.nextToken());
            nodeData2 = Integer.parseInt(st.nextToken());
            nodes.get(nodeData1).add(nodeData2);
            nodes.get(nodeData2).add(nodeData1);
        }

 

여기서 두 개의 노드를 교차해서 입력해주었는데, 이는 입력되는 노드들의 순서가 '부모 → 자식' 순인지, '자식 → 부모' 순인지 보장이 안되어있기 때문에 어느쪽에서든 탐색이 가능하도록 하기 위함이었습니다.

 

이후에는 루트 노드 1을 시작으로 연결된 노드들을 탐색하면서, 자식과 부모 노드 관계를 설정해주도록 했습니다. 이때 HashMap을 이용했습니다. 또한 탐색 시 방문 처리를 하면서 같은 노드를 한번 더 방문하지않도록 했습니다. 이는 방금 전 두 개의 노드를 교차해서 입력함으로 인해 발생하는 중복 탐색을 방지하도록 해줍니다.

 

        // ...
        boolean[] visited = new boolean[n + 1];
        makeNode(1, visited);
        // ...
    }

    private static void makeNode(int parent, boolean[] visited) {
        visited[parent] = true;

        for (int i = 0; i < nodes.get(parent).size(); i++) {
            int child = nodes.get(parent).get(i);
            if (!visited[child]) {
                parentByNode.put(child, parent);
                makeNode(child, visited);
            }
        }
    }

 

소스 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

class Main {

    static int n;
    static List<List<Integer>> nodes = new ArrayList<>();
    static Map<Integer, Integer> parentByNode = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n + 1; i++) {
            nodes.add(new ArrayList<>());
        }

        StringTokenizer st;
        int nodeData1, nodeData2;
        for (int i = 1; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            nodeData1 = Integer.parseInt(st.nextToken());
            nodeData2 = Integer.parseInt(st.nextToken());
            nodes.get(nodeData1).add(nodeData2);
            nodes.get(nodeData2).add(nodeData1);
        }

        boolean[] visited = new boolean[n + 1];
        makeNode(1, visited);

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = 2; i < n + 1; i++) {
            bw.write(String.valueOf(parentByNode.get(i)));
            bw.write('\n');
        }

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

    private static void makeNode(int parent, boolean[] visited) {
        visited[parent] = true;

        for (int i = 0; i < nodes.get(parent).size(); i++) {
            int child = nodes.get(parent).get(i);
            if (!visited[child]) {
                parentByNode.put(child, parent);
                makeNode(child, visited);
            }
        }
    }
}

 

(번외) 인접 행렬을 이용한 풀이 - 메모리 초과

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

class Main {

    static int n;
    static boolean[][] nodes;
    static Map<Integer, Integer> parentByNode = new HashMap<>();

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

        n = Integer.parseInt(br.readLine());
        nodes = new boolean[n + 1][n + 1];

        StringTokenizer st;
        int nodeIndex1, nodeIndex2;
        for (int i = 1; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            nodeIndex1 = Integer.parseInt(st.nextToken());
            nodeIndex2 = Integer.parseInt(st.nextToken());
            nodes[nodeIndex1][nodeIndex2] = true;
            nodes[nodeIndex2][nodeIndex1] = true;
        }

        makeNode(1);

        for (int i = 2; i < n + 1; i++) {
            System.out.println(parentByNode.get(i));
        }
    }

    private static void makeNode(int parent) {
        for (int i = 1; i < n + 1; i++) {
            if (nodes[parent][i]) {
                nodes[parent][i] = false;
                nodes[i][parent] = false;
                parentByNode.put(i, parent);
                makeNode(i);
            }
        }
    }
}

 

참고 자료

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