[백준] 11725번 : 트리의 부모 찾기

문제

 

 

접근 방식

그래프에서의 BFS/DFS와 조금만 다르게 코드를 짜면 트리를 순회할 수 있는

BFS/DFS 코드를 만들 수 있다.

 

기존에 그래프에서는 이전에 방문한 정점인지 확인하기 위해

불리언이나 정수형 배열을 통해 방문 여부를 기록해두었다면

트리는 방문 여부를 확인하는 것이 아니라 부모가 기록 되었는지로

방문 여부를 확인할 수 있다.

 

기존 BFS/DFS 코드와 마찬가지로 구성은 같지만

다음에 방문할 자식 노드에 부모가 누구인지만 기록해주면 된다.

 

BFS와 DFS 방식 모두 구현해보았는데 그래프 때도 느꼈지만

재귀 방식인 DFS가 코드가 뭔가 깔끔해서 보기가 좋다.

 

풀이

public class Main {

	private static int n;
	private static int[] p;
	private static final ArrayList<ArrayList<Integer>> nearList = new ArrayList<>();
	private static StringTokenizer st;
	private static final StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		input();
		bfs();
		dfs(1, 0);
		append();
		System.out.println(sb);
	}

	private static void bfs() {
		p = new int[n + 1];

		Queue<Integer> q = new ArrayDeque<>();
		q.offer(1);

		while (!q.isEmpty()) {
			int cur = q.poll();

			for (int next : nearList.get(cur)) {
				if (p[cur] == next) continue;
				q.offer(next);
				p[next] = cur;
			}
		}

		sb.append("BFS").append("\n");

		append();

		sb.append("\n");
		sb.append("DFS").append("\n");
		p = new int[n + 1];
	}

	private static void dfs(int cur, int parent) {
		p[cur] = parent;

		for (int next : nearList.get(cur)) {
			if (p[cur] == next) continue;
			dfs(next, cur);
		}
	}

	private static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		n = Integer.parseInt(br.readLine());
		int x, y;

		for (int i = 0; i <= n; i++) {
			nearList.add(new ArrayList<>());
		}

		for (int i = 0; i < n - 1; i++) {
			st = new StringTokenizer(br.readLine());

			x = Integer.parseInt(st.nextToken());
			y = Integer.parseInt(st.nextToken());

			nearList.get(x).add(y);
			nearList.get(y).add(x);
		}
	}

	private static void append() {
		for (int i = 2; i <= n; i++) {
			sb.append(p[i]).append("\n");
		}
	}
}