[백준/파이썬] 11725번

민정·2023년 4월 26일
0

[백준/파이썬]

목록 보기
135/245
post-thumbnail

📍백준 11725번 문제

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

코드

# 시간초과 코드
import sys
input = sys.stdin.readline

n = int(input())
tree = {1: []}
for i in range(n-1):
    n1, n2 = map(int, input().split())
    if n1 in list(tree.keys()):  # 루트 노드로 있는 경우
        tree[n1] += [n2]
        continue
    elif n2 in list(tree.keys()):
        tree[n2] += [n1]
        continue
    for i in list(tree.values()):
        if n1 in i:
            tree[n1] = [n2]
        elif n2 in i:
            tree[n2] = [n1]
    # if tree[n2]:
    #     tree[n2] += n1
for i in range(2, n+1):
    for key, value in tree.items():
        if i in list(value):
            print(key)
# 정답 코드
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

for _ in range(n-1):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
visited = [0] * (n+1)

arr = []


def dfs(x):
    for i in graph[x]:
        if visited[i] == 0:
            visited[i] = x
            dfs(i)


dfs(1)

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

풀이

  • 시간 초과 :
    이중 for문 때문이 아닐까 싶다.
    이 문제를 dfs로 해결해야 한다고 생각을 하지 못했다.
profile
パㅔバ6ㅇr 덤벼ㄹΓ :-0

0개의 댓글