[S2] 트리의 부모 찾기 : Java : 11725 -DFS

문제

11725번: 트리의 부모 찾기

---

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 접근

  전체 노드를 탐색하면서 어떻게 부모 노드를 저장할 수 있을까! 생각을 해봤을 때 자식 노드를 탐색하기 위해 재귀 함수를 호출할 때 부모의 값을 넘겨주면 될 것이라고 생각했다! 

 

  모든 노드를 탐색해야 하기 때문에 DFS와 BFS 중 고민했고 함수를 호출할 때 부모의 값을 넘겨주면 구현하기 쉬울 것이라 생각해서 재귀함수를 쓰는 DFS를 사용했다. 

void DFS(int child, int p) {
        visited[child] = true;
        // 부모 값을 저장
        parent.set(child, p);
        Iterator<Integer> iterator =  adj[child].iterator();
        while (iterator.hasNext()){
            int n = iterator.next();
            if(!visited[n]){
            // 자기를 호출한다 -> 부모이다
                DFS(n, child);
            }
        }
    }

 

 

---

 

 

 

 

 

 

 

 

전체 코드 - Java

import java.awt.*;
import java.io.*;
import java.util.*;


public class Main {

    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 정점의 수
        int N = Integer.parseInt(st.nextToken());

        Graph graph = new Graph(N+1);

        for(int i=0; i< N-1; i++){
            st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            graph.addEdge(v,w);
        }

        graph.DFS(1, 0);

        for(int i =2; i< graph.parent.size(); i++){
            System.out.println(graph.parent.get(i));
        }
    }


}
class Graph{
    int v;
    LinkedList []  adj;
    boolean [] visited;
    ArrayList parent;

    Graph(int v){
        this.v = v;
        this.visited = new boolean[v+1];
        adj = new LinkedList[v];
        parent = new ArrayList();
        for(int i=0; i<v; i++){
            adj[i] = new LinkedList();
            parent.add(i,0);
        }
    }

    void addEdge(int v, int w){
        if(!adj[v].contains(w))
            adj[v].add(w);
        if(!adj[w].contains(v))
            adj[w].add(v);
    }

    void DFS(int child, int p) {
        visited[child] = true;
        parent.set(child, p);
        Iterator<Integer> iterator =  adj[child].iterator();
        while (iterator.hasNext()){
            int n = iterator.next();
            if(!visited[n]){
                DFS(n, child);
            }
        }
    }

}