[BOJ] 11725. 트리의 부모 찾기

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

---

접근 방법

stack을 이용한 DFS 방식으로 풀었다. 나는 DFS를 너무 사랑하는 듯.

각 부모 노드 번호를 저장할 배열과 check 배열을 통합시키기 위해 int 배열을 사용했다.

0이 아닌 수로 방문 처리를 하는 것이다.

 

소스 코드

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

public class Main {	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.valueOf(br.readLine());
		ArrayList<Integer>[] g = new ArrayList[N+1];
		int[] check = new int[N+1];
		
		for(int i=0; i<=N; i++) {
			g[i] = new ArrayList<>();
		}
		
		for(int i=0; i<N-1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int n = Integer.valueOf(st.nextToken());
			int m = Integer.valueOf(st.nextToken());
			g[n].add(m);
			g[m].add(n);
		}
		
		Stack<Integer> s = new Stack<>();
		s.push(1);
		check[1] = 1;
		
		while(!s.isEmpty()) {
			int now = s.peek();
			boolean hasNode = false;
			
			for(int i : g[now]) {
				if(check[i] == 0) {
					hasNode = true;
					s.push(i);
					check[i] = now;
					break;
				}
			}
			if(!hasNode)
				s.pop();
		}
		
		for(int i=2; i<=N; i++)
			bw.write(check[i] + "\n");
		bw.close();
	}
}