https://www.acmicpc.net/problem/1135
상사 id가 있는 리스트가 주어지고, 한 사람당 전화할 때 1분씩 걸린다고 했을 때 뉴스 최종 전파의 최소 시간을 구하는 문제이다.
코드 1 - 실패
정렬이긴 했는데, 트리로 생각하면 더 빠를 것 같아서 게다가 최소 시간을 구하는 문제라서 BFS를 사용하기로 결정했다.
from collections import defaultdict
n = int(input())
parent = list(map(int, input().split()))
company = defaultdict(list)
for i, v in enumerate(parent):
if i:
company[v].append(i)
que = [(0, 0)]
idx =0
while idx < len(que):
now, time = que[idx]
idx += 1
for i, v in enumerate(company[now]):
que.append((v, time + 1 + i))
print(que)중간에 테스트 하다가 멈춘 코드이다. 부하직원의 id 순서대로 전화하는 과정을 bfs que에 담는 과정으로 구현했는데, index를 통해서 앞에 부하직원 전화하는 동안 기다린 시간을 더해줬다.
그런데 이렇게 하니까
24
-1 0 0 1 1 1 2 2 3 3 4 4 5 5 6 7 7 8 12 13 14 16 16 16이 경우에서 답은 7이 나와야하는데, 9가 나왔다.
5
-1 0 0 2 2다른 경우인 여기서는 답은 3인데, 내 코드는 4를 출력했다.
문제 상에서는 부하직원을 순서대로 전화한다는 조건이 없었는데 그걸 간과했다.
두 번째 테스트케이스에서 2번 부하직원 먼저 전화하면 3이 나오는데 그걸 고려해야할 것 같다.
코드 2 - 실패
상사별로 부하직원이 총 몇 명있는지 계산해줬다.
for i in range(n-1, 0, -1):
child[parent[i]] += child[i] + 1그러고 bfs돌면서 que에 부하직원을 추가해주기 전에 부하직원 많은 순서대로 추가될 수 있도록 했다.
while idx < len(que):
now, time = que[idx]
idx += 1
company[now].sort(key=lambda x: -child[x])
for i, v in enumerate(company[now]):
que.append((v, time + 1 + i))이렇게 하니까 문제에 제시된 테스트케이스는 모두 통과하는데 틀렸다고 나왔다.
15
-1 0 0 0 0 2 2 3 3 6 7 7 4 12 13위 테스트케이스를 찾았는데 답은 5이지만 내 코드는 6을 출력했다. 단순 부하직원 수로는 안 되는 것 같다.
코드 3 - 실패
단계가 문제인가 싶어서 바꿔봤는데도 실패했다.
for i in range(n-1, 0, -1):
if child[parent[i]] == 0:
child[parent[i]] += child[i] + 1코드 4 - DFS
GPT가 DFS로 해보라고 했다.
from collections import defaultdict
n = int(input())
parent = list(map(int, input().split()))
company = defaultdict(list)
for i in range(1, n):
company[parent[i]].append(i)
def dfs(e):
if not company[e]:
return 0
times = []
for child in company[e]:
times.append(dfs(child))
max_time = 0
times.sort(reverse=True)
for i, t in enumerate(times):
max_time = max(max_time, t + i + 1)
return max_time
print(dfs(0))그냥 전체를 돌면서 부하 직원들 중 가장 긴 시간을 뽑아서 반환하고 거기에 추가 연산하는 방식을 사용했다.
times를 정렬한 이유는 시간 제일 오래 걸리는 부하직원한테 먼저 전화해줘야 그나마 빠르게 끝날 수 있기 때문이다.
max_time 계산할 때는
해당 부하직원이 그 아래 직원에게 전화하는 시간 +
전화해주는데 걸리는 시간 1분 +
다른 사원들 전화 끝날 때까지 기다리는 시간 index분이렇게 해서 구했다.
최소 시간이라길래 BFS로 고정하고 접근했는데, 다양한 방식을 사용해봐야겠다.
