[Baekjoon] 11725_트리의 부모 찾기

Silver II

문제(출처: https://www.acmicpc.net/problem/11725)

---

<트리의 부모 찾기>

문제 

 

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

 

 

입력

 

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

 

출력 

 

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

 

 

문제 풀이

- 초기 코드: 시간 초과

 

import sys

def bfs(graph, start, result):
    visited=[start]
    queue=[start]
    while queue:
        temp=queue.pop(0)
        for i in graph[temp]:
            if i not in visited:
                visited.append(i)
                result[i-1]=temp
                queue.append(i)

if __name__=='__main__':
    n=int(input()) # 노드의 개수

    graph={1:[]} # 트리의 루트

    for i in range(n-1):
        x,y=map(int ,sys.stdin.readline().split()) # 연결된 두 정점
        if x not in graph:
            if y in graph:
                graph[y].append(x)
                graph[x]=[]
        elif y not in graph:
            if x in graph:
                graph[x].append(y)
                graph[y]=[]

    result=[0]*n
    bfs(graph, 1,result)

    for i in range(1,n):
        print(result[i])

 

❓ 어디서 시간 초과가 발생했는가?

시간 초과가 발생한 부분을 찾지 못해 검색을 해보니 not in과 append를 사용하면서 시간이 오래 걸릴 수도 있다는 것을 발견하였다.

그래서 방문을 하면 list에 넣어주던 코드를 처음부터 모든 노드를 False로 선언한 후 방문했으면 True로 바꿔주도록 하는 코드로 고쳤더니 시간 초과는 해결할 수 있었다.

 

❓ 그럼 왜 틀렸는가?

예외를 고려하지 못했다. 내가 구현한 코드는 입력이 차례대로 잘 들어와야 결과가 제대로 나오는 코드였다.

만약 입력받는 부분에서 아직 dict의 key값에 없는 값들이 나왔다면 그 노드들은 출력에서 0이 나올 것이다.

예를 들면 

5

1 3

2 4

3 4

2 5

와 같은 예제이다. 이 경우 2의 부모 노드가 4가 출력되어야 하지만 위의 코드로는 0이 출력될 것이다.

 

이 부분을 해결하는데 오랜 시간이 걸렸다. 진짜 오래 걸린 것 같지만 사실 1시간밖에 안 지났다는 것에 충격 먹음

처음에는 노드 두 개 값 다 key값에 없다면 노드 두 개를 맨 뒤로 보내는 방법을 택하였다. 

구현하면서도 시간 초과 날 것임을 확신했지만 혹시 몰라 도전해봤다.

결과는 53%에서 시간 초과 발생

 

정말 몰라 검색의 힘을 빌렸다. 왜 이 간단한 생각을 못했나 싶을 정도로 단순하게 양방향으로 dict에 값을 넣어주면 된다는 아주 큰 hint를 얻어버렸다. 위와 같은 나의 코드에서 양방향으로 넣어주는 부분만 수정하면 바로 통과할 수 있었다.

 

 

- my solution

 

import sys

def bfs(graph, start, result):
    visited=[False]*len(result) # 방문 여부
    visited[start-1]=True
    queue=[start]
    while queue:
        temp=queue.pop(0)
        for i in graph[temp]:
            if visited[i-1]==False: # 아직 방문하지 않았다면
                visited[i-1]=True # 방문
                result[i-1]=temp # 부모 노드 저장
                queue.append(i)

if __name__=='__main__':
    n=int(input()) # 노드의 개수

    graph={}
    for i in range(1,n+1):
        graph[i]=[]

    for i in range(n-1):
        x,y=map(int ,sys.stdin.readline().split()) # 연결된 두 정점
        graph[x].append(y)
        graph[y].append(x)

    result=[0]*n
    bfs(graph, 1,result)

    for i in range(1,n):
        print(result[i])

 

위의 틀린 코드보다 더 간단해진 통과한 코드이다.

• bfs
  : visited = 방문 여부 확인하는 list
  : queue가 빌 때까지 반복 = 제일 처음 값을 pop 해서 그와 연결된 노드를 방문하지 않았다면 방문 후 부모 노드 저장 및 queue에 저장
• main
  : 노드의 개수 입력
  : 노드의 개수만큼 dict에 key 생성
  : 연결된 두 정점 입력 - 부모 노드가 누구인지 모르므로 양방향으로 저장
  : result = 부모 노드 저장할 list

---

생각🤔

 

몇 번의 고비와 검색의 힘을 빌렸지만 그래도 해결해서 마음이 편안해졌다.

가끔은 단순하게 생각해보자

 

---