반응형
트리의 부모 찾기
-
BOJ) 트리의 부모 찾기 (11725, JAVA)알고리즘/백준 2020. 8. 25. 17:58
트리의 부모 찾기 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 처음에는 1차원 배열로 문제를 풀려고 하다가, 연결 관계에서 부모 관계를 파악하기 힘들다는 문제를 발견했다. 그래서 BFS로 풀어야겠다는 마음을 먹었다. 우선 map을 저장해줘야 하는데, 배열을 사용할 수 없다. (최악의 경우 100,000 by 100,000가 된다) 그래서, ArrayList 배열에 map의 관계를 저장했다. (레코드 조회만 필요하기 때문에 ArrayList가 더 적절하다고 판단했다.) 맵이 저장된 다음에는 Queue를 통해 부모를 짝지어주었다. root인 1부터 시작하면서 1과 연결..