[백준] 11725 트리의 부모 찾기 - 트리(Tree) + DFS(깊이우선탐색) JAVA

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

11725번: 트리의 부모 찾기

코드설명

트리(Tree) + DFS(깊이우선탐색)를 활용합니다.

 

트리의 루트노드는 1번 노드로 고정되어 있습니다.

그렇기에, 1번 노드부터 시작하여 다음에 만나는 노드의 부모값을 재귀함수에 넣어두면서 함꼐 갱신시키면 됩니다.

 

여기서, N의 크기는 100,000 (10^5) 십만 이기에 matrix 행렬로 그래프를 만들면 10^10 으로 메모리초과 256MB 를 초과하여 ArrayList<Integer>[] 형태로 만들어줍니다.

코드

코드입니다.

import java.util.ArrayList;
import java.util.Scanner;
public class Main {
	
	static boolean[] visited;
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	static int[] answer;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		visited = new boolean[n+1];
		answer = new int[n+1];
		for(int i=0;i<=n;i++) {
			graph.add(new ArrayList<Integer>());
		}
		
		for(int i=1;i<n;i++) {
			int start = sc.nextInt();
			int end = sc.nextInt();
			graph.get(start).add(end);
			graph.get(end).add(start);
		}
		
		
		dfs(1, 1);
		
		for(int i=2;i<=n;i++) {
			System.out.println(answer[i]);
		}
	}
	
	static void dfs(int start, int parent) {
				
		visited[start] = true;
		answer[start] = parent;		
		for(int i=0; i<graph.get(start).size();i++) {
			if(visited[graph.get(start).get(i)] == false) {
				dfs(graph.get(start).get(i), start);
			}else {
				continue;
			}
		}
		
	}

}

 

정답코드 2입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
	static int N, C, H, W, K, M, T;
	static int answer = 0;
	static int[] parent;
	static ArrayList<Integer>[] arr;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		arr = new ArrayList[N];
		for(int i=0;i<N; i++) {
			arr[i] = new ArrayList<Integer>();
		}
		parent = new int[N];
		for(int i=0;i<N-1; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken()) - 1;
			int v = Integer.parseInt(st.nextToken()) - 1;
			arr[u].add(v);
			arr[v].add(u);
		}
		
		DFS(0, -1, new boolean[N]);
		for(int i=1; i<N; i++) {
			System.out.println(parent[i] + 1);
		}
	}
	
	static void DFS(int now, int before, boolean[] visited) {
		
		parent[now] = before;
		for(int next = 0; next < arr[now].size(); next++) {
			int nextNode = arr[now].get(next);
			if(visited[nextNode] == false) {
				visited[nextNode] = true;
				DFS(nextNode, now, visited);
			}
		}
		
	}
	
}

2차원 행렬로 받을경우 10^5 (십만) * 10^5 이기에 메모리초과가 발생합니다.

흠.. 256MB이기에 2^20 * 2^8 이 10^10 * 1 Byte 보다 작기에 메모리초과가 발생합니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, C, H, W, K, M, T;
	static int answer = 0;
	static int[] parent;
	static boolean[][] matrix;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		matrix = new boolean[N][N];
		parent = new int[N];
		for(int i=0;i<N-1; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken()) - 1;
			int v = Integer.parseInt(st.nextToken()) - 1;
			matrix[u][v] = true;
			matrix[v][u] = true;
		}
		
		DFS(0, -1, new boolean[N]);
		for(int i=1; i<N; i++) {
			System.out.println(parent[i] + 1);
		}
	}
	
	static void DFS(int now, int before, boolean[] visited) {
		
		parent[now] = before; 
		for(int next=0; next<N; next++) {
			if(matrix[now][next] == true && visited[next] == false) {
				visited[next] = true;
				DFS(next, now, visited);
			}
		}
		
	}
	
}