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

문제

• 트리의 부모 찾기(백준11725)

풀이

문제 해석을 하자면,

• 입력 받는 트리의 부모 노드를 찾는 문제이다.

풀이

• 먼저, 노드 1을 시작으로 BFS를 사용해서 높이(level tree)를 구한다.

• 이후 출력할 때 높이 비교를 통해서 부모인지 판단한다.

코드

/**
 * 1. 노드 1을 시작으로 BFS를 사용해서 높이(level tree)를 구한다.
 * 2. 출력할 때 높이 비교를 통해서 부모인지 판단한다.
 */

static List<Integer>[] inArr = new ArrayList[100005];
static int[] level = new int[100005];
static boolean[] visited = new boolean[100005];

static void bfs() {
    // init
    Arrays.fill(level, -1);
    Queue<Integer> qu = new LinkedList<>();
    qu.add(1);
    visited[1] = true;
    level[1] = 0;

    while(!qu.isEmpty()) {
        int cur = qu.peek(); qu.remove();
        for(int nxt : inArr[cur]) {
            if(visited[nxt]) continue;
            qu.add(nxt);
            visited[nxt] = true;
            level[nxt] = level[cur] + 1;
        }
    }
}

public static void main(String[] args) throws IOException {
    // input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk;
    int N = Integer.parseInt(br.readLine());
    for(int i = 0; i<=N; i++) inArr[i] = new ArrayList<>(); // init
    for(int i = 0 ;i <N-1;i++) {
        stk = new StringTokenizer(br.readLine(), " ");
        int a = Integer.parseInt(stk.nextToken());
        int b = Integer.parseInt(stk.nextToken());
        inArr[a].add(b);
        inArr[b].add(a);
    }
    // run
    bfs(); // level 구하기
    // output
    StringBuilder sb = new StringBuilder();
    for(int i = 2; i<=N; i++) {
        int root = 1000000;
        for(int nxt : inArr[i]) {
            if(level[i]-level[nxt] == 1) { // 부모인지 확인
                root = Math.min(root,nxt); // 여러 부모일 경우 최소 노드를 기억
            }
        }
        sb.append(root).append('\n');
    }
    System.out.println(sb);
}

느낀점

생략