DFS

import sys 
sys.setrecursionlimit(10**6) 
n = int(sys.stdin.readline()) 

graph = [[] for i in range(n+1)] 

for i in range(n-1): # 그래프를 만들어서 각 그래프 좌표에 연결 지점의 좌표를 넣는다.
	a, b = map(int, sys.stdin.readline().split()) 
    graph[a].append(b) 
    graph[b].append(a) 
    
visited = [0]*(n+1) 
arr = [] 

def dfs(s): # 연결되어 있는 지점들을 방문하고 현재 지점 = 부모 노드를 저장해놓는다.
	for i in graph[s]: 
    	if visited[i] == 0: 
        	visited[i] = s 
            dfs(i) 
            
dfs(1) 

for x in range(2, n+1): 
	print(visited[x])

BFS

import sys
from collections import deque

sys.stdin = open('input.txt', 'rt')
input = sys.stdin.readline

N = int(input())
graph = [[] for k in range(N + 1)]
visited = [False] * (N + 1)

for _ in range(N - 1):
    a, b = map(int, input().split())

    graph[a].append(b)
    graph[b].append(a)

queue = deque([1])

while queue:
    num = queue.popleft()

    for i in graph[num]:
        if visited[i] == False:
            visited[i] = num
            queue.append(i)

for i in range(2, N+1):
    print(visited[i])

핵심인 것은 처음에 2차원 배열로 나타냈었다.

graph = [[0 for i in range(N + 1)] for k in range(N + 1)]
for _ in range(N - 1):
    a, b = map(int, input().split())

    graph[a][b] = graph[b][a] = 1

하지만 이 문제는 노드의 개수가 최대 100,000개 이므로 이차원 배열에서 연결상태를 표시하게 되면 10만*10만 = 100억개의 칸을 사용하기 때문에 메모리 초과가 날 수 밖에 없어 append로 추가해주는 방식으로 변경했다.