Baekjoon 11725 트리의 부모 찾기 JAVA

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

11725번: 트리의 부모 찾기

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%2011725

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 그래프가 주어지고 루트 노드가 1이라고 했을 때

2부터 N까지의 노드들의 부모 노드가 누군지

출력하는 문제다.

​

처음의 문제를 보고 union find를 이용하면 되겠다고 생각했는데

문제를 풀고 제출하니 시간 초과가 발생했고

이후 인접 행렬과 bfs를 이용했더니 이번엔 메모리 초과가 발생해서

이것저것 시도하다가 결국 다른 사람들이 한걸 보았는데

ArrayList를 배열처럼 사용해서 문제를 해결하는 걸 확인하고

동일하게 진행해서 문제를 해결했다.

​

ArrayList를 배열을 이용해 각 노드와 연결된 노드 정보를 넣어준 뒤

bfs를 진행하면 된다.