(JAVA) 백준 11725번 : 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

11725, 트리의 부모 찾기

이번 문제는 트리 구조와 BFS(너비우선탐색) 을 사용하면 풀 수 있는 문제이다.

그다지 어렵지 않다.

 

N의 범위가 2 이상, 100,000 이하 이기 때문에 int 형을 사용해 주겠다.

# Process

main

: 트리상에서 연결된 두 정점을 제공하기 때문에 양방향으로 연결해주면 된다.

ArrayList 를 사용한 인접 리스트 방식으로 코드를 구현하겠다.

( adj의 i 번째의 공간에 ArrayList 생성 )

static void input() 
{
    n = scan.nextInt();
    adj = new ArrayList[n + 1];
    parent = new int[n + 1];
    for (int i = 1; i <= n; i++) adj[i] = new ArrayList<>();

    // 인접 리스트 구성하기
    for (int i = 1; i < n; i++) {
        int x = scan.nextInt(), y = scan.nextInt();
        
        // 연결된 두정점, 양방향
        adj[x].add(y);
        adj[y].add(x);
    }
}

 

dfs

: 정점 (x) 과 부모 (par) 로 인자로 받아 해당 ArrayList 를 모두 탐색한다.

여기서 adj 안에는 부모가 있기 때문에 이런 케이스는 제외해준다.

나머지 경우에는 parent라는 배열에 자식을 index로, 부모를 값으로 넣어준다.

그 후 dfs 를 재귀호출 해주면 모든 원소들을 탐색할 수 있다.

static void dfs(int x, int par) 
{
    for (int y : adj[x]) 
    {
        if (y == par) continue;

        parent[y] = x;
        dfs(y, x);
    }
}

 

마지막으로 1번은 root 이기 때문에 2 번째 요소부터 N 번째 요소까지 parent 의 값을 호출하면 된다.

// 정답 출력하기
for (int i = 2; i <= n; i++) sb.append(parent[i]).append('\n');

System.out.println(sb);

 

 

 

급하게 조사하고 정리하다보니 부족하거나 틀린 내용이 있을 수도 있는데 댓글로 달아주시면 감사하겠습니다!