[BOJ] 11725번 트리의 부모 찾기

개요

2차원배열 탐색은 익숙하지만 그래프 탐색이 취약해서 풀어본 문제

트리를 탐색하여 모든노드의 부모노드를 찾는 문제이다.

문제링크

코드

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Baekjoon11725 {
    public static ArrayList<Integer>[] tree;
    public static int[] parents;
    public static boolean[] isVisited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        tree = new ArrayList[n+1];
        parents = new int[n+1];
        isVisited = new boolean[n+1];
        StringTokenizer st;
        for (int i = 0; i < tree.length; i++) 
            tree[i] = new ArrayList<>();
        
        int from, to;
        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            from = Integer.parseInt(st.nextToken());
            to = Integer.parseInt(st.nextToken());

            tree[from].add(to);
            tree[to].add(from);
        }

        isVisited[1] = true;
        dfs(1);
        
        for (int i = 2; i < parents.length; i++) 
            bw.write(parents[i]+"\n");
        bw.flush();

        
    }

    public static void dfs(int node) {
        int child;
        for (int i = 0; i < tree[node].size(); i++) {
            child = tree[node].get(i);
            if(!isVisited[child]) {
                parents[child] = node;
                isVisited[child] = true;
                dfs(child);
            }
        }
    }
}

해결 과정

트리 탐색은 트리의 정점마다 연결된 다른 정점들을 저장해두고 확인하는 것이 일반적인데

자바에서는 List의 배열을 이용해 간편하게 저장할 수 있다.

입력으로 두 정점의 데이터를 받으면 list[node1].add(node2) 을 해주고 그 반대의 경우도 추가해준다.

즉 다음과 같이 받으면 된다.

int from, to;
for (int i = 0; i < n - 1; i++) {
    st = new StringTokenizer(br.readLine());
    from = Integer.parseInt(st.nextToken());    //정점1
    to = Integer.parseInt(st.nextToken());      //정점2

    tree[from].add(to); //정점1에 연결된 정점의 목록에 정점2를 추가
    tree[to].add(from); //정점2에 연결된 정점의 목록에 정점1를 추가
}

이 다음에는 깊이우선탐색을 통해 모든 노드들을 한번씩 방문하면서 부모노드를 배열에 저장하면 된다.

재귀 방식을 이용해 구현하였는데 이 때 노드의 방문유무를 체크하는 것이 중요하다.

public static void dfs(int node) {
    int child;
    for (int i = 0; i < tree[node].size(); i++) {
        child = tree[node].get(i);  //node의 자식노드
        if(!isVisited[child]) { //자식노드를 방문하지 않았으면
            parents[child] = node;      //부모노드 저장
            isVisited[child] = true;    //방문표시
            dfs(child);
        }
    }
}

이후엔 부모노드를 저장한 배열(parents[])을 출력해주면 해결된다.

결과