#14267 내리 갈굼

출처: https://www.acmicpc.net/problem/14267

14267번: 내리 갈굼

 

번호가 작을수록 상사이고 노드(직원)끼리 직속 상관관계인 간선을 벡터로 연결한 후에 

1번부터 n번 직원까지 갈굼의 정도를 출력하는 문제이다.

 

처음에는 간선 연결 후에 단순 dfs 즉 완전탐색을 통해 방문하는 노드마다 갈굼 점수를 해당 노드에 더하는 방식으로 구현했었다. 하지만 이렇게 할 경우 시간초과가 난다.

 

시간초과 소스코드

 

 

하지만 방식을 바꿔서 1번부터 n번까지 반복문을 돌려주면서 어차피 번호가 작을수록 상사이므로 1번상사부터 내리갈굼을 차례차례 축적시켜 나가면 탐색 횟수를 이전보다 훨씬 효과적으로 줄일 수 있다.

 

예를들어 

1-2-4

   |

   3 -5

 

와 같이 연결이 돼 있다고 하고 2,3이 2의 크기로 갈굼을 각각 초기에 당했다고 하면

2번은 1번한테 받은 2의 갈굼을 3,4에 전달한다. 그래서 4의 갈굼값은 처음 0이였다가 2로 바뀌고

3번은 초기 2번한테서 받은 갈굼 2에다가 2번이 1번한테 갈굼받은 값 2도 받게되어 총 4가 축적이된다. 그리고 3번은 이 4의 갈굼을 그대로 5번에 전달해 주게 된다.

이렇게 갈굼값을 순차적으로 축적시키면서 다음 사람에게 전달하는 방식으로 해주게되면 1부터 n까지 모든 간선이 연결이 되 있으면 총 2n번의 반복을 수행하게되어 O(n)의 시간복잡도로 문제를 해결할 수 있게 된다.