[백준] 단계별로 풀어보기(단계:29, 트리,JAVA)11725번, 트리의 부모 찾기

문제 링크

11725번: 트리의 부모 찾기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

트리

서로 다른 두 노드를 잇는 길이 하나뿐인 그래프

트리 구조 - 위키백과, 우리 모두의 백과사전

 

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

BFS

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

 

이 문제에 핵심은

1. 트리에 대한 정보를 가지고 각 정점에 부모 노드 번호를 결과로 출력해야합니다.

2. 트리의 루트 정점은 항상 1이다.

 

루트 정점인 1번에서부터 BFS탐색을 시작하여 각 정점에 부모 정점을 구합니다.

 

예제입력1에 대한 트리

1. 루트 정점 1에서 탐색

연결되는 정점 4, 6을 탐색합니다.

4와 6의 부모 노드의 값을 1을 저장합니다.

 

 

2. 먼저 Queue에 들어간 정점 4에서 탐색

연결되는 정점 2, 7을 탐색합니다.

2와 7의 부모 노드의 값을 4을 저장합니다.

3. 정점 6 탐색

연결되는 정점 3을 탐색합니다.

3의 부모 노드의 값을 6을 저장합니다.

3. 정점 2, 7은 연결된 정점 없으므로 정점 3 탐색

연결되는 정점 5을 탐색합니다.

5의 부모 노드의 값을 3을 저장합니다.

정점 2~N까지의 부모 노드들의 값을 결과로 출력합니다.\

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해 트리에 대한 정보를 저장하였습니다.
• BFS로 루트 정점 1부터 탐색하는 bfs함수를 만들었습니다.
• BufferedWriter에 2~N까지 부모 정점에 대한 결과를 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs은 visited[]를 통해 루트 정점 1에서부터 트리에 탐색을 진행합니다.
• bfs는 각 정점에 도착했을 때 부모 정점을 result에 저장하였습니다.

결과 코드

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

public class Main {
	static int N;
	static ArrayList<ArrayList<Integer>> tree = new ArrayList<>();	//트리의 값 저장
	static boolean[] visited;	//트리 정점 방문 확인
	static int[] result;	//각 정점 부모 정점 확인
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
    	StringTokenizer st;
    	N = Integer.parseInt(br.readLine());
    	result = new int[N+1];
    	visited = new boolean[N+1];
        //트리 값 저장
    	for(int i=0;i<=N;i++) 
    		tree.add(new ArrayList<Integer>());
    		
    	for(int i=1;i<N;i++) {
    		st = new StringTokenizer(br.readLine()," ");
    		int point1 = Integer.parseInt(st.nextToken());
    		int point2 = Integer.parseInt(st.nextToken());
    		tree.get(point1).add(point2);
    		tree.get(point2).add(point1);
    	}
    	bfs(1);		//루트 정점 1에서부터 BFS 탐색 시작
        //2~N의 정점의 부모 노드의 값을 BufferedWriter 저장
    	for(int i=2;i<=N;i++)
    		bw.write(result[i] + "\n");
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //BFS 탐색을 수행하는 함수
    static void bfs(int start) {
    	Queue<Integer> queue = new LinkedList<Integer>();
    	visited[start] = true;	//시작 정점 방문 확인
    	queue.add(start);	
    	while(!queue.isEmpty()) {
    		int root = queue.poll();
    		for(Integer next : tree.get(root)) {	//해당 정점 탐색
    			if(!visited[next]) {
    				visited[next] = true;
    				result[next] = root;
    				queue.add(next);
    			}
    		}
    	}
    	return;
    }
}