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

1. 문제

---

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

11725번: 트리의 부모 찾기

 

 

 

---

 

 

 

2. 코드 구현 부분

---

• 예를들어, 루트 노트 1에 방문하였을 때
  • 루트 노드 1의 인덱스는 0이다. 따라서 0번 인덱스에는 3과 5가 존재한다. 즉, 4와 6이 인접한 노드인 것이다.
  • 1이 루트 노드이므로 4와 6은 자식 노드이다.
  • 1번 노드에 방문하였으므로 visited 배열에서 인덱스 0은 true로 변환한다.
• 예를 들어, 노드 4에 방문하였을 때
  • 노드 4의 인덱스는 3이다. 현재 인덱스 3에는 0, 1, 6의 데이터가 존재한다. 즉 인접한 노드는 1,2,6이다.
  • 이 중 1은 이미 visited 배열이 true 이므로 방문을 하였던 노드이다 따라서 1은 4의 부모노드인 것이다.
  • 남은 노드2 와 노드 7은 자식노드이므로 2와 7의 부모 노드는 4인 것이다.

 

 

import java.util.*;

class Main{
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();     // 노드의 개수 N
        ArrayList<ArrayList<>> tree = new ArrayList<>();  // 트리 구조를 표현하기위해 객체 생성
        
        for(int i=0; i<n ;i++) {
        	tree.add(new ArrayList<Integer>());    //각 인덱스 별 배열을 생성한다.
        }
        for(int i=0; i<n-1;i++) {    //입력을 n-1번 받기 때문에 n-1번 반복
        	int n1 = sc.nextInt() - 1;    //인덱스로 변환하기 위해 -1 실행
            int n2 = sc.nextInt() - 1;
            tree.get(n1).add(n2);
            tree.get(n2).add(n1);
        }
        boolean[] visited = new boolean[n];    // 방문여부를 파악하기 위한 배열
        int[] parents = new int[n];    // 부모노드에 해당하는 값을 저장하기 위한 배열
        
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);     // 루트노드 추가
        visited[0] = true;     // 루트노드의 방문은 true로 설정
        while(!queue.isEmpty()) {
        	int tmp = queue.remove();
            for(int node: tree.get(tmp)) {
            	if(!visited[node]) {
               	    visited[node] = true;
                    queue.add(node);
                    parents[node] = tmp;
                }
            }
        }
        for(int i = 1; i<n ; i++) {   //루트노드를 제외한 나머지를 출력하기 위해 1부터 시작
        	System.out.println(parents[i] + 1);
        }
    }
}