[Algorithm] 백준 1516 게임개발 파이썬

---

📌아이디어 & 틀 생각하기

해당 문제는 사이클이 없는 방향 그래프이다. -> 시간복잡도가 O(V+E)인 위상 정렬을 사용해서 찾으면 되겠다고 생각했다.

위상정렬을 사용한 간단한 슈도코드 짜기
1. 인접리스트, 진입차수리스트, 위상정렬 큐 생성
2. 인접리스트를 이용해 진입차수 계산
3. 진입차수가 0인 노드 선택후 선택된 노드를 위상정렬 큐에 넣는다.
4. 큐에서 노드 정보를 빼낸 후
5. 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입차수를 1 빼기
5-1. 만약 진입차수가 0이라면 큐에 선택된 노드 추가
큐가 빌 때 까지 4~5 반복

📌작성한 코드(오답)

from collections import deque

N = int(input())
A = [[] for _ in range(N + 1)]
D = [0] * (N + 1) # 진입차수 리스트 
Time = [0] * (N + 1)

for i in range(1, N + 1):
  inputList = list(map(int, input().split()))
  Time[i] = inputList[0]
  index = 1
  while True:
    if inputList[index] == -1:
      break
    A[inputList[index]].append(i)
    D[i] += 1
    index += 1

queue = deque()

for i in range(1, N + 1):
  if D[i] == 0:
    queue.append(i)

while queue:
  now = queue.popleft()
  for next in A[now]:
    D[next] -= 1
    if D[next] == 0:
      Time[next] += Time[now]
      queue.append(next)

for i in range(1, N + 1):
  print(Time[i])

---

📌 오답이유 확인

건물이 동시에 지어질 수 있다는 내용이 있었다.

from collections import deque

N = int(input())
A = [[] for _ in range(N+1)]
D = [0]*(N+1)
BuildTime = [0]*(N+1) # 시간
result = [0]*(N+1)
#변수이름을 변경했습니다. Time > result , BuildTime 추가 

for i in range(1,N+1):
    inputList = list(map(int, input().split()))
    BuildTime[i] = inputList[0]
    index = 1
    
    while True:
        preTemp = inputList[index]
        index += 1
        if preTemp == -1:
            break
        A[preTemp].append(i)
        D[i] += 1
    
q = deque()

for i in range(1, N+1):
    if D[i] == 0:
        q.append(i)

while q :
    now = q.popleft()
    for next in A[now]:
        D[next] -= 1
        result[next] = max(result[next], result[now]+BuildTime[now])
        
        if D[next] == 0:
            q.append(next)

for i in range(1,N+1):
    print(result[i] + BuildTime[i])

📌중요한 부분 톺아보기

1. 시간 업데이트 시 max함수를 사용하여 동시에 지어질 때 경우를 생각하기.