[JAVA] 백준 (실버2) 11725번 트리의 부모 찾기

링크

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

---

문제 설명

정답률 42.451%
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

---

입력 예제

• 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다.
• 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

7
1 6
6 5
3 5
4 1
2 4
4 7

---

출력 예제

• 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

4
5
1
6
1
4

---

풀이

예제를 그래프로 나타내면 다음과 같다.

우선 인접 리스트로 그래프를 구현하고 각 노드의 부모 노드를 구하기 위해 bfs를 이용한다.

코드

//백준
public class Main {

    static int[] parents;
    static boolean[] visit;
    static List<List<Integer>> adjList;

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());  //노드의 수
        adjList = new ArrayList<>();  //인접 리스트
        for (int i = 0; i < N + 1; i++) {
            adjList.add(new ArrayList<>());
        }

        //인접 리스트 구현
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            adjList.get(a).add(b);
            adjList.get(b).add(a);
        }

        parents = new int[N + 1];  //각 노드의 부모 노드
        visit = new boolean[N + 1];
        bfs();

        Arrays.stream(parents)
                .skip(2)  //맨 앞 2개 원소 제외
                .forEach(System.out::println);
    }

    static void bfs() {

        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);  //루트 노드 추가

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            visit[cur] = true;

            for (Integer i : adjList.get(cur)) {
                if (!visit[i]) {
                    parents[i] = cur;
                    queue.add(i);
                }
            }
        }

    }

}