[java 백준] 실버 2/ 11725번 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

 import java.io.BufferedReader; 
      
 import java.io.IOException; 
      
 import java.io.InputStreamReader; 
      
 import java.util.ArrayList; 
      
 import java.util.LinkedList; 
      
 import java.util.List; 
      
 import java.util.Queue; 
      

          
      
 public class Main { 
      

          
      

            public static int N; 
      

          
      

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

                BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
      

                N = Integer.parseInt(br.readLine()); 
      

                List<Integer> list[] = new ArrayList[N + 1]; 
      

                for (int i = 0; i < N + 1; i++) { 
      

                    list[i] = new ArrayList<Integer>(); 
      

                } 
      

                for (int i = 0; i < N - 1; i++) { 
      

                    String s = br.readLine(); 
      

                    String[] str = s.split(" "); 
      

                    int a = Integer.parseInt(str[0]); 
      

                    int b = Integer.parseInt(str[1]); 
      

                    list[a].add(b); 
      

                    list[b].add(a); 
      

          
      

                } 
      

          
      

                boolean visit[] = new boolean[N + 1]; 
      

                Queue<Integer> queue = new LinkedList<Integer>(); 
      

          
      

                queue.add(1); 
      

                visit[1] = true; 
      

                int ans[] = new int[N + 1]; 
      

                while (!queue.isEmpty()) { 
      

                    int num = queue.poll(); 
      

                    for (int i : list[num]) { 
      

                        if (!visit[i]) { 
      

          
      

                            visit[i] = true; 
      

                            ans[i] = num;// i가 노드값 num이 부모값 
      

                            queue.add(i); 
      

                        } 
      

                    } 
      

                } 
      

          
      

                for (int i = 2; i < ans.length; i++) { 
      

                    System.out.println(ans[i]); 
      

                } 
      

          
      

            } 
      

          
      

        } 
      

          
      

처음에는 Tree 클래스 만들어서 node.parent, node.child 일일이 다 생각해줬는데
문제의 핵심은 결국 부모만 찾으면 됐다.

그래서 list[노드값]={노드값에 해당하는 자식들의 원소}인 List를 만들어주고
BFS를 통해 인접노드를 확인하면서 ans[노드값]=노드값의 부모에 해당하는 값 인 배열 ans을
만들어서 마지막에 for문만 돌려주면 됐다.

List<Integer> list[] = new ArrayList[];

--> 이 형태가 생각보다 그래프에서 유용하게 사용되는듯하다

1991번에도 위의 사진처럼 똑같은 형식의 풀이가 있었는데 기억해야 할듯하다
https://we1cometomeanings.tistory.com/180

[java 백준] 실버 1/ 1991번 트리 순회

이런형식은 List안에 ArrayList가 하나 더 있는 형식인데, 이것을 그림으로 나타내면

이런식으로 된다
list[a].add(b)와 list[b].add(a)로 저장되어있는 것을 시각화 시키면

이 다음 for(int i:list[num]을 통해 인접노드를 BFS로 파악해주면된다.

참고자료

https://ilmiodiario.tistory.com/142

[백준] 11725. 트리의 부모 찾기 (자바 JAVA)