[백준] 11725번 : 트리의 부모 찾기 - 자바(JAVA)

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

11725번: 트리의 부모 찾기

 

문제 해석

루트가 없는 트리가 주어집니다.

이때 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오

 

 

문제 풀이 전 설계

우선 그래프 탐색 문제라고 생각을 했습니다.

따라서 2차원 배열 graph [i][j]를 선언하고 정점 i와 정점 j가 연결되어있으면 1 그렇지 않으면 0으로 표기합니다.

 

문제 풀이 하면서 생각한 점

하지만 우리가 원하는 것은 부모의 노드를 찾아야 합니다.

단순히 graph 2차원 배열에 정점이 연결된 것만으로는 부모의 노드를 구할 수 없어

1부터 시작해서 BFS로 자식을 탐색하여 parentArray [i]에 i노드의 부모 값을 저장합니다.

 

graph 2차원 배열 생성 시 N의 범위가 10만입니다.

따라서 메모리 초과 오류가 발생하였습니다.

• int arr [10,000][10,000]이 대략 400MB이기 때문에 배열을 사용하면 안 될 것 같습니다

 

따라서 인접 행렬을 포기하고 Link라는 클래스를 만들어 edgeA, edgeB를 저장하였습니다.

하지만 이 경우에도 시간 초과가 발생하였습니다.

이 경우는 로직이 뭔가 꼬여서 무한루프 시간 초과일 수도 있다는 생각을 했습니다.

따라서 인접 리스트를 통해 DFS를 구현하여 해결했습니다.

 

DFS 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main_11725_트리의부모찾기 {
	static int N;
	static boolean[] visited;
	static int[] parentArray;
	static List<ArrayList<Integer>> edgeList;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		inputGraph();		
		DFS(1);
		printResult();

	}

	static void inputGraph() throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		visited = new boolean[N + 1];
		edgeList = new ArrayList<ArrayList<Integer>>();
		for (int i = 0; i < N+1; i++) {
			edgeList.add(new ArrayList<Integer>());
		}
		parentArray = new int[N + 1];
		for (int node = 0; node < N - 1; node++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int edgeA = Integer.parseInt(st.nextToken());
			int edgeB = Integer.parseInt(st.nextToken());			
			edgeList.get(edgeA).add(edgeB);
			edgeList.get(edgeB).add(edgeA);
		}

	}

	static void DFS(int node) {
		visited[node] = true;
		
		for (int e : edgeList.get(node)) {
			if (visited[e]) {
				continue;
			}
			parentArray[e] = node;
			DFS(e);
		}
	}

	

	static void printResult() throws IOException {
		StringBuilder sb = new StringBuilder();
		for (int i = 2; i < parentArray.length; i++) {
			sb.append(parentArray[i] + "\n");
		}
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		bw.write(sb.toString());
		bw.flush();

	}

}