백준 11725 문제 풀이

문제링크: https://www.acmicpc.net/problem/11725

사용한 자료구조 : 그래프

BFS를 사용하기 위해 그래프를 사용하였다.

---

찾아낸 규칙

주어진 트리는 무방향 그래프이므로 양쪽으로 연결정보를 저장해준다.
ex) 입력
7
1 6
6 3
3 5
4 1
2 4
4 7

0	1	2	3	4	5	6	7
	[6, 4]	[4]	[6, 5]	[1, 2, 7]	[3]	[1,3]	[4]

또한 무방향 그래프이므로 자식에서 부모, 부모에서 자식으로 가는 방향이 없으므로 방문 배열을 만들어 방문 여부를 체크할수 있도록 하여 부모/자식을 구분해 준다.

---

코드 및 코드 설명

package pre;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class FindTreesParent {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 노드 개수를 입력 받는다.

        ArrayList<Integer>[] conn = new ArrayList[n+1]; // index 노드와 연결된 노드들을 저장
        int[] parent = new int[n+1]; // index 노드의 부모를 저장할 배열
        boolean[] visited = new boolean[n+1]; // 방문 여부를 체크할 배열

        for(int i = 0; i<n+1; i++){ // conn 초기화
            conn[i] = new ArrayList<>();
        }
        
		// 연결 정보 입력
        for(int i = 1; i<n; i++){ // 연결 정보를 입력 받고 저장한다.
            int node1 = sc.nextInt(); 
            int node2 = sc.nextInt();
            
			// 무방향 그래프이므로 양쪽으로 저장해준다.
            conn[node1].add(node2);
            conn[node2].add(node1);
        }
        
		// BFS
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1); // 루트 노드를 큐에 넣고 시작
        visited[1] = true; // 루트 노드를 방문했으므로 체크
        while(!queue.isEmpty()){
            int now = queue.poll(); // 현재 노드
            for(int child : conn[now]){ // 현재 노드와 연결된 노드들을 순회하면서
                if(visited[child]){ // 방문한 적이 있다면 넘어가고
                    continue;
                }
                parent[child] = now; // 방문한 적이 없다면 child노드의 부모를 현재노드로 저장한다.
                queue.add(child); // child노드를 큐에 넣는다.
                visited[child] = true; // 방문 체크
            }
        }

        for(int i = 2; i<n+1; i++){ // 2번 노드부터 부모노드를 출력한다.
            System.out.println(parent[i]);
        }

    }
}

시행착오 및 교훈

아직 문제를 보고 트리를 구성하는 것이 어렵다. 또한 BFS나 DFS를 바로 적용하기가 어렵다. 적용하더라도 DFS나 BFS를 재귀로 구현하는것을 잘 모르겠다. 앞으로 관련 문제를 더 풀어보면서 내것으로 만들어야겠다!