[Python] 🥈백준 트리의 부모 찾기 - 11725 /DFS 알고리즘

예제 입력 1

7
1 6
6 3
3 5
4 1
2 4
4 7

예제 출력 1

4
6
1
3
1
4

 

아이디어 생각하기

 

 

그래프를 만들고, 방문여부를 체크하는 배열 visited를 선언한다.

루트 v를 dfs() 인수로 넘겨 V와 연결된 다른 노드를 재귀적으로 방문한다. 

for문으로 그래프를 도는데, 만약 visited[v]가 비어있다면, visited했다는 의미의 True가 아닌, 탐색을 시작한 값 즉, 부모를 넣어준다.

그리고 다시 재귀한다.

 

결국, dfs를 기존 그대로구현하고, visited에는 방문여부대신, v를 넣어주면 된다! 기존의 로직을 헷갈릴 것 같아서

변수명은 그대로 visited로 냅두고 진행하겠다

원한다면  father, parents 등으로 바꿔보자....

 

주의사항

graph = [[0] * (n+1) for _ in range(n*2)]                                                                                                                         
for i in range(n):
  x,y = map(int, input().split())
  graph[x][y] =1 #[[1][2], [2][3], [3][4]]
  graph[y][x] =1

이차원 배열을 만들 때 이런식으로 이중 배열을 만들면 메모리 초과가 생긴다!

graph = [[] for _ in range(n+1)]
for _ in range(n-1):  # 간선수는 n-1개
    x, y = map(int, input().split())  # [[1,2], [2,3] .....]
    graph[x].append(y)
    graph[y].append(x)

이런식의 이중배열을 만들어 메모리를 초과를 예방하자

 

 

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8) #재귀 리미트

n = int(input())

# 그래프 만들기
graph = [[] for _ in range(n+1)]
for _ in range(n-1):  # 간선수는 n-1개
    x, y = map(int, input().split())  # [[1,2], [2,3] .....]
    graph[x].append(y)
    graph[y].append(x)
visited = [0] * (n+1) #방문여부 대신, 부모를 담을 변수


# dfs 함수
def dfs(v):
   # 현재 V와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:  # 방문하지 않은 노드라면
            # visited를 1이 아닌, 탐색을 시작한 값을 넣어준다 dfs는 항상 부모에서 자식으로 이동한다.
            visited[i] = v
            dfs(i)  # 해당 노드를 시작 노드로 dfs

dfs(1) #항상 1이 시작노드

# visited 출력
for i in range(2, n+1):
    print(visited[i])