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

[Solved]/BOJ

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

응파카 2023. 3. 23. 23:21

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

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

문제를 푸시다보면 다양한 에러를 만나실텐데요. 오늘은 백준알고리즘 1697번을 풀면서 발생한 메모리 초과에 대해서 글을 써보려고 합니다. 메모리 초과가 발생하는 이유를 간단히 말씀드리자

programmers-story.tistory.com

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

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 트리의 부모 찾기

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net import ja

sedangdang.tistory.com

이 분처럼 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]);
		}
	}

}

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

다음부터는 문제를 풀 때

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

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

저작자표시

'[Solved] > BOJ' 카테고리의 다른 글

[백준 1927] 최소 힙 (0)	2023.04.28
[백준 1464] 뒤집기 3 (0)	2023.04.26
[백준 5430] AC (0)	2023.04.26
[백준 1021] 회전하는 큐 (0)	2023.03.31
[백준 1991] 트리순회 (0)	2023.03.25

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

응파카 성장일지

JPA프로그래밍 기본편, Favor 프로젝트, 김영한의 Spring, priorityqueue, string, BOJ, JPA 프로그래밍, coding test, JPA, 오블완, spring, Heap, Stack, 플래너, Java, JPA프로그래밍 기초, 코딩테스트, inheritance, Deque, 티스토리챌린지,

Today :
Yesterday :

응파카 성장일지