백준_트리의 부모 찾기_11725

//알고리즘

1. 그래프 탐색 (트리)

 

2. 인접리스트를 만들고 방문배열을 만듦

 

3. 탐색시작

 -> bfs를 사용하여 구현

 -> 매번 탐색하면서 부모노드를 찾으면 방문배열을 매번 새롭게 생성하여야 하기 때문에 시간초과가 남

 -> 해당노드의 부모노드를 저장하는 배열을 만들어 bfs를 한번 돌면서 각 노드의 부모노드를 저장

 

package baekjoon;

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

public class 트리의부모찾기_11725 {

	static int N, ans[];
	static ArrayList<Integer>[] list;

	static class Point {
		int prev, start;
		
		

		public Point(int start) {
			super();
			this.start = start;
		}


		public Point(int start, int end) {
			super();
			this.prev = start;
			this.start = end;
		}

	}

	static Queue<Point> q;

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		ans = new int[N+1];
		list = new ArrayList[N + 1];
		q = new LinkedList<Point>();

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

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

			list[start].add(end);
			list[end].add(start);
		}

		bfs(1, new boolean[N + 1]);
		
		for (int i = 2; i <= N; i++) {
			System.out.println(ans[i]);
		}

	}

	private static void bfs(int idx, boolean[] v) {
		v[idx] = true;
		q.add(new Point(idx));

		Point p = null;
		while (!q.isEmpty()) {
			p = q.poll();

			ans[p.start] = p.prev;

			int size = list[p.start].size();
			for (int i = 0; i < size; i++) {

				if (v[list[p.start].get(i)])
					continue;
				v[list[p.start].get(i)] = true;
				q.add(new Point(p.start,list[p.start].get(i)));
			}
		}

	}

}

 

※ 처음에 매번탐색을 하면서 정답을 구하니 시간초과가 남, 정답배열을 만들어 해결하였음 ( 매번 방문배열을 생성하는데 시간이 걸림 -> 이전에 작성한 글에 비슷한 경우가 있었는데 또 생각 못하고 구현함). 이전에 비슷하게 시간초과를 해결한 경험으로 이번엔 빨리 수정할 수 있었음. 한번 더 생각하고 코드를 구현해서 실수를 줄여나가야겠다.