[백준 11275] 트리의 부모찾기

https://programmers-story.tistory.com/10

[백준 알고리즘] 메모리 초과 발생 이유 및 해결 방안

단순한 탐색 문제로 생각하고 인접행렬을 사용해 다음과 같이 풀었더니 메모리 초과가 나왔다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	//문제에서 N의 범위가 2~10만이기 때문에 인접 그래프로 하면 메모리 초과
	
	static int node;
	static boolean[][] graph;
	static boolean[] isVisited;
	static int[] parentArr;
	static Stack<Integer> stack = new Stack<>();
	
	public void DFS(int parent, int start) {
		stack.push(start);
		parentArr[start] = parent;
		isVisited[start] = true;
		
		while(!stack.isEmpty()) {
			int temp = stack.pop();
			isVisited[temp] = true;
			for(int i=1; i<=node; i++) {
				if(!isVisited[i] && graph[temp][i]==true) {
					stack.push(i);
					parentArr[i] = temp;
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException{
		Main T = new Main();
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		node = Integer.parseInt(bufferedReader.readLine());
		
		graph = new boolean[node+1][node+1];
		isVisited = new boolean[node+1];
		parentArr = new int[node+1];
		
		for(int i=1; i<=node-1; i++) {
			StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
			int vertex1 = Integer.parseInt(stringTokenizer.nextToken());
			int vertex2 = Integer.parseInt(stringTokenizer.nextToken());
			graph[vertex1][vertex2] = true;
			graph[vertex2][vertex1] = true;
		}

		T.DFS(0, 1);
		
		for(int i=2; i<=node; i++) System.out.println(parentArr[i]);
	}

}

문제를 다시 읽어보니 N의 범위가 2~100,000 이었다.

10만이 주어졌을 때 인접리스트의 element 개수만 100.000^2 일테니 메모리 초과가 나는게 당연했다.

 

 

 

 

 

이를 해결하기 위해 이번에는 다음과 같이 메모리를 덜 사용하는 리스트를 사용했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static int n;
	static boolean[] isVisited;
	static int[] parentArr;
    
    	//이차원 배열 -> LinkedList<LinkedList<>
	static LinkedList<LinkedList<Integer>> graph = new LinkedList<>();
    
	
	public void BFS(int start) {
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(start);
		isVisited[start] = true;
		while(!queue.isEmpty()) {
			int temp = queue.poll();
			for(Integer x : graph.get(temp)) {
				if(!isVisited[x]) {
					parentArr[x] = temp;
					isVisited[x] = true;
					queue.add(x);
				}
			}
		}
		
	}

	public static void main(String[] args) throws IOException {
		Main T = new Main();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		isVisited = new boolean[n+1];
		parentArr = new int[n+1];
		
		for(int i=1; i<=n+1; i++) {
			graph.add(new LinkedList<>());
		}
		

		for(int i=1; i<=n-1; i++) {
			StringTokenizer stk = new StringTokenizer(br.readLine());
			int vertex1 = Integer.parseInt(stk.nextToken());
			int vertex2 = Integer.parseInt(stk.nextToken());
			graph.get(vertex1).add(vertex2);
			graph.get(vertex2).add(vertex1);
		}
		
		T.BFS(1);
		
		for(int i=2; i<=n; i++) System.out.println(parentArr[i]);
		
		
	}

}

메모리 초과는 해결했지만 이번에는 시간초과가 떴다.

 

한참을 생각해도 원인을 잘 모르겠어서 검색을 했고 다음 링크에서 힌트를 찾았다.

 

 

https://sedangdang.tistory.com/m/122

[JAVA] # 11725 트리의 부모 찾기

 

이 분처럼 LinkedList<LinkedList>를 -> ArrayList의 배열로 고치고 나니 시간초과 문제가 해결되었다.

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.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static int n;
    
 	//ArrayList[] 로 변경
	static ArrayList<Integer>[] graph;
    

	static boolean[] isVisited;
	static int[] parentArr;
	
	public void BFS(int start) {
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(start);
		isVisited[start] = true;
		while(!queue.isEmpty()) {
			int temp = queue.poll();
			for(Integer x : graph[temp]) {
				if(!isVisited[x]) {
					parentArr[x] = temp;
					isVisited[x] = true;
					queue.add(x);
				}
			}
		}
		
	}

	public static void main(String[] args) throws IOException {
		Main T = new Main();
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		n = Integer.parseInt(br.readLine());
		isVisited = new boolean[n+1];
		parentArr = new int[n+1];
		graph = new ArrayList[n+1];
		
		for(int i=0; i<n+1; i++) graph[i] = new ArrayList<>();

		for(int i=0; i<n-1; i++) {
			StringTokenizer stk = new StringTokenizer(br.readLine());
			int vertex1 = Integer.parseInt(stk.nextToken());
			int vertex2 = Integer.parseInt(stk.nextToken());
			graph[vertex1].add(vertex2);
			graph[vertex2].add(vertex1);
		}
		
		T.BFS(1);
		
		for(int i=2; i<=n; i++) {
			System.out.println(parentArr[i]);
		}
		
		
	}

}

List 인 graph를 탐색하는것과 배열인 graph를 탐색하는 속도의 차이가 10만 이라는 범위의 테스트테이스에서 큰 차이를 낸 모양이다.

 

 

이번에는 탐색에 있어서 배열과 같이 O(1) 만큼의 시간복잡도를 갖는 ArrayList는 어떨지 ArrayLisy<ArrayList> 로 실행해보았다.

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

public class Main {
	
	static int n;
    
    	//ArrayList[] -> ArrayList<ArrayList<>>
	static ArrayList<ArrayList<Integer>> graph;
    
	static boolean[] isVisited;
	static int[] parentArr;
	
	public void BFS(int start) {
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(start);
		isVisited[start] = true;
		while(!queue.isEmpty()) {
			int temp = queue.poll();
			for(Integer x : graph.get(temp)) {
				if(!isVisited[x]) {
					parentArr[x] = temp;
					isVisited[x] = true;
					queue.add(x);
				}
			}
		}
		
	}

	public static void main(String[] args) throws IOException {
		Main T = new Main();
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		n = Integer.parseInt(br.readLine());
		isVisited = new boolean[n+1];
		parentArr = new int[n+1];
		graph = new ArrayList<>();
		
		for(int i=0; i<n+1; i++) graph.add(new ArrayList<>());

		for(int i=0; i<n-1; i++) {
			StringTokenizer stk = new StringTokenizer(br.readLine());
			int vertex1 = Integer.parseInt(stk.nextToken());
			int vertex2 = Integer.parseInt(stk.nextToken());
			graph.get(vertex1).add(vertex2);
			graph.get(vertex2).add(vertex1);
		}
		
		T.BFS(1);
		
		for(int i=2; i<=n; i++) {
			System.out.println(parentArr[i]);
		}
	}

}

배열과 마찬가지로 통과했다.

 

다음부터는 문제를 풀 때

 

1. 주어진 값의 범위에 따른 메모리 제한
2. 탐색 혹은 데이터 추가면에 있어서 어떤 방법이 더 효율적인지

이 두 가지를 고려하며 문제를 풀어야겠다.