백준 11725(트리 부모찾기)

처음에는 Node 의 클래스 생성을 통해 트리구조를 만들고 찾아가는 방식을 사용하였다.

이렇게 할 경우 자식의 list 를 반복문으로 다 찾아야하기 때문에 시간초과가 되는 오류가 발생했다.

실행시간을 줄이기 위해 그래프구조의 DFS 방식을 사용하였다.

​

<답은 나오지만 백준 프로그램 채점 시 시간 초과 오류 발생한 코드>

import java.util.LinkedList;
import java.util.Scanner;


public class Main {
	
	static int n;
	static Node tree;
	
	public static void main(String[] args){
		
		Scanner scanner = new Scanner(System.in);
		
		n = scanner.nextInt();
		
		String line = null; 
		line = scanner.nextLine();
		for(int i = 0 ; i < n - 1 ; i++) {
			line = scanner.nextLine();
			String[] alpha = line.split(" ");
		
			if(i == 0) {
				if(alpha[0].equals("1")) {
					tree = new Node(alpha[0]);
					Node child = new Node(alpha[1]);
					tree.addChild(child);
				}
				else {
					tree = new Node(alpha[1]);
					Node child = new Node(alpha[0]);
					tree.addChild(child);
				}
			}
			else {
				Node head = findNode(tree, alpha[0], alpha[1]);
				
				if(head.getData().equals(alpha[0])) {
					Node new_node = new Node(alpha[1]);
					head.addChild(new_node);					
				}
				else {
					Node new_node = new Node(alpha[0]);
					head.addChild(new_node);
				}
			}
		}
		
		
		for(int i = 2 ; i <= n; i++) {
			Node parent = findParent(tree, Integer.toString(i));
			
			if(parent != null)
				System.out.println(parent.getData());
		}
		
		
	}
	
	public static Node findParent(Node head, String data) {
		
		Node result = null;
		
		if(head.getList() != null) {
			for(int i = 0 ; i < head.getLength(); i++) {
				Node child = head.getChild(i);
				
				if(child.getData().equals(data))
					return head;
				else {
					result = findParent(child, data);
					if(result != null)
						break;
				}
			}
		}
		
		return result;
	}
	
	public static Node findNode(Node head, String data1, String data2) {
		Node result = null;
		
		if(head.getData().equals(data1) || head.getData().equals(data2)) {
			return head;			
		}
		
		LinkedList list = head.getList();
		for(int i = 0 ; i < list.size() ; i++) {
			Node child= (Node) list.get(i);
			result = findNode(child, data1, data2);
			if(result != null)
				break;
		}
		
		return result;
	}
}

class Node{
	
	private LinkedList<Node> childList;
	private String data;
	
	public Node(String data) {
		childList = new LinkedList<Node>();
		this.data = data;
	}
	
	public String getData() {
		return this.data;
	}
	
	public void setData(String data) {
		this.data = data;
	}
	
	public LinkedList<Node> getList(){
		return this.childList;
	}
	
	public void addChild(Node child) {
		this.childList.add(child);
	}
	
	public int getLength() {
		return this.childList.size();
	}
	
	public Node getChild(int i) {
		return childList.get(i);
	}
}

<DFS 방식으로 바꾼 코드, 구글링 코드 참고하였다>

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	
	static int n;
	static boolean[] visit;
	static List<Integer>[] list;
	static int[] parents;
	
	public static void main(String[] args){
		
		Scanner scanner = new Scanner(System.in);
		
		n = scanner.nextInt();
		
		list = new ArrayList[n+1];
		parents = new int[n+1];
		
		for(int i = 1; i <= n ; i++) {
			list[i] = new ArrayList<>();
		}
		
		visit = new boolean[n+1];
		
		for(int i = 1 ; i < n ; i++) {
			int a = scanner.nextInt();
			int b = scanner.nextInt();
			list[a].add(b);
			list[b].add(a);
		}
		
		DFS(1);
		
		for(int i = 2 ; i <= n ; i++) {
			System.out.println(parents[i]);
		}
	}
	
	public static void DFS(int v) {
		visit[v] = true;
		
		for(int i : list[v]) {
			
			if(!visit[i]) {
				parents[i] = v;
				DFS(i);
			}
		}
	}
}