BOJ_11725_트리의 부모 찾기

1

구분: 그래프 이론, 그래프 탐색, 트리, 너비우선탐색, 깊이 우선탐색

언어: Java

전략

• 루트 노드인 1부터 시작
• 노드들 간 연결 요소를 ArrayList배열을 이용 - 각 배열마다 ArrayList선언 필요
• 자신과 연결된 노드들 이 내 자식이다 
• 부모의 번호를 담을 배열을 준비한다
• 나와 연결되어 있는데, 이미 부모가 설정된것(나의 부모이다). 그렇지 않은 것들의 부모를 저장
• bfs: 한 노드에서 자신과 연결된 모든 노드를 바로 자식으로 여기기 때문에 

---

2. 코드 

import java.util.Scanner;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static int[] parent; //부모를 담을 배열
	static ArrayList<Integer>[] list;//연결 관계를 나타낼 리스트 배열
	static int n;//전체 노드의 수 
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		
		//배열이기 떄문에 각 배열마다 
		list = new ArrayList[n+1];
		for(int i = 0; i<=n; i++) {
			list[i] = new ArrayList<>();
		}
		
		//입력을 받는다. 양방향 연결이다 
		for(int i = 0; i<n-1; i++) {
			int a = scanner.nextInt();
			int b = scanner.nextInt();
			list[a].add(b);
			list[b].add(a);
		}
		
		bfs();
		
		//2번부터 출력
		for(int i = 2; i<=n; i++) {
			System.out.println(parent[i]);
		}
		
	}//main
	
	private static void bfs() {
		Queue<Integer> q = new LinkedList();
		parent = new int[n+1];
		q.add(1);
		parent[1] = 1;
		
		while(!q.isEmpty()) {
			//현재 노드 번호
			int cur = q.poll();
			//각 노드와 연결된 수 
			int size = list[cur].size();
			
			//연결된 것들을 돌면서 
			for(int i = 0; i<size; i++) {
				int temp = list[cur].get(i);
				//만약 이미 부모가 정해져 있다면 지나가 
				if(parent[temp] != 0) continue;
				//이것의 부모를 나 자신으로 한다 
				parent[temp] = cur;
				q.add(temp);
			}
		}
	}
}

---

3

• 메모리 초과가 났다.
• 노드들 간 연결을 나타내는 방법 - 인접 리스트, 인접 행렬 모두 사용해보았다
• 내가 사용하는 인접행렬이 문제일 것 같다고 판단하였다 

	//연결 리스트를 위해 시도한 형태
    static class Node{
		int vertex; 
		Node link;
		Node(int vertex, Node link){
			this.vertex = vertex;
			this.link = link;
		}
	}
	static Node[] list;

• ArrayList배열을 사용하니 메모리 초과가 발생하지 않았다 
• 요즘 문제를 풀면 메모리 초과, 시간 초과가 나는데 조금 슬프다