BOJ_S2_11725

📁 [S2_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;
import java.util.StringTokenizer;

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

		// **** input start ****
		int N = Integer.parseInt(br.readLine());

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

		for(int i=0; i<list.length; i++) {
			list[i] = new ArrayList<Integer>();
		}

		for(int i=0; i<N-1; i++) {
			st = new StringTokenizer(br.readLine()," ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			list[a].add(b);
			list[b].add(a);
		}

		// **** input end ****

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

		// BFS
		Queue<Integer> queue = new LinkedList<Integer>();
		// 루트 값
		queue.add(1);
		// 방문처리
		v[1] = true;
		// 결과 저장 배열
		int[] res = new int[N+1];

		while(!queue.isEmpty()) {
			// 현재 ArrayList 출력 ( 연결되어있는 곳 )
			Integer num = queue.poll();
			// ArrayList for문
			// i 는 값들 ( list 안에 있는 값들 )
			for(Integer i : list[num]) {
				// 방문안했으면
				if(!v[i]) {
					// 방문처리
					v[i] = true;
					// 결과 값에 부모 넣어주기
					res[i] = num;
					queue.add(i);
				}
			}
		}

		// 출력
		for(int i=2; i<res.length; i++) {
			System.out.println(res[i]);
		}
	}
}

🤔 나의 생각

이 문제는 값 마다 ArrayList를 통해 연결되어 있는 값들을 저장해서 BFS를 통해 값을 구해 배열에 저장하는 방법으로 풀었다.
과정은 다음과 같다.

• 먼저 list에 ArrayList를 저장해준다. list[ ArrayList<> , ArrayList<> … ] ( 연결된 모든 값들을 저장 )
• 값들을 쌍방으로 넣어준다.
• 방문체크할 배열을 생성한다. boolean[] v
• BFS를 통해 값을 가져와서 for문을 돌며 부모를 찾아 배열에 저장해준다.
• 배열에 모든 값을 출력해준다.

이 문제에서 List에 ArrayList를 삽입하여 모든 연결된 값들을 저장하는게 포인트 인 것 같다.
BFS 안에서도 for문을 돌면서 리스트 값들을 돌면서 방문처리를 해주며 결과 배열에 값을 넣어주는 것이다.