그저께 케빈 문제 풀고 뭔가 멘탈이 나갔는지뭔지 하도 안 잡혀서 한 문제만 풀고 자려고 잡은 문제다! 그런데 이 문제도 바로 딱 풀긴 풀었는데 시간 초과가 나서 고생을 좀 했다 ..ㅎ 다른 분들 풀이를 보고 아..! 했다 나도 꼭 저렇게 되야지..! 생각하고 있다.
문제 설명
이 문제는 직속 상사가 후배한테 칭찬을 해줄 때마다 그 칭찬이 내리사랑처럼 후배한테 계속 전달 전달 되어서 칭찬이 누적되고, 모든 칭찬 릴레이? 가 끝난 후 각 회사원이 받은 칭찬의 누적 값을 출력하는 문제이다. 따라서 bfs보다는 dfs를 써서 내리사랑을 표현해야겠구나! 라는 생각이 바로 든다. 그래서 dfs를 반복해서 돌면서? 칭찬을 누적하면 되겠구나 생각할 수 있다. 나 역시도 dfs라는 걸 알고 반복문으로 dfs를 실행하는 코드를 짰었다.
문제 풀이
그러나 dfs를 for문 안에서 반복해서 실행하면 시간 초과가 난다. dfs가 최대 100000번 실행될 수 있으므로,, 어쩌면 당연한 결과라고 볼 수도 있다. 그래서 시간 초과가 나지 않도록 dfs를 딱 한번 실행하는 방법을 이용한다. 이 방법은 여기를 참고하였다. 링크 처음엔 이 방법을 보고 와우… 대박… 획기적 이란 생각을 했고 내가 혼자 풀면 이 방법을 생각해 낼 수 있는가?에 대한 고민도 좀 했었다. 그렇다면 dfs를 딱 한번 실행해서 어떻게 할 수 있는가?가 궁금할 수 있다. 이거는 회사원 a가 받은 칭찬이 그 상사에게는 절대 전달되지 않고 오로지 a의 후배들한테만 전달된다는 걸 생각해보면 이해가 조금 편하다. 가장 먼저 특정 회사원 i가 받은 칭찬(칭찬이 여기서부터 시작된다)을 초기에 이미 더해주고 시작한다. 이렇게 되면, a가 받은 칭찬은 a의 후배들에게 모두 전달되어야 하므로 a가 내리사랑해줄때는 a가 받은 칭찬을(위의 모든 상사들에게서 받은 칭찬들) 모두 a의 후배들에게 보내주면 된다. a의 직속 후배를 b라고 해보자. 그럼 b는 a의 내리사랑을 받은 상태이고, b가 b의 직속 후배에게(a의 후배이기도 한) b가 받았던 모든 칭찬들(여기에는 a가 준 칭찬도 포함되어 있을 것이고, a가 준 것 이외에 b가 주는 칭찬, 즉 초기에 이미 더해주고 시작한 값)를 전달해 주면 반복해서 돌지 않아도 칭찬들이 쭉쭉 내려가면서 모두 전달이 된다. 결국 뭐 정점을 방문했는지 안했는지를 따질 필요도 없고 그냥 회사원 a가 받은 칭찬을 a의 직속자식들에게 모두 똑같이 전달해주면 된다. 칭찬이 밑으로 갈수록 점점 늘어나는 이유는 내려갈수록 상사들이 초기에 이미 더해준 칭찬을 후배들이 계속 합쳐져서 받기 때문이다.
풀이는 아래와 같다. v[100001]을 사용할 필요가 없다.
1 | |
