백준 1005 ACM Craft 파이썬 풀이

난이도 : 골드3

풀이일 : 05033

https://www.acmicpc.net/problem/1005

1005번: ACM Craft

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

1차 시도 오답 -> 4% 틀렸습니다

import sys
from collections import deque

def sol(queue):
    while queue:
        i = queue.popleft()
        for j in child[i]:
            total[j] = max(total[i] + time[j], total[j])
            queue.append(j)
            count[j] -= 1
            if not count[w-1]:
                return print(total[w-1])

T = int(sys.stdin.readline().strip())
for tc in range(T):
    N, K = map(int, sys.stdin.readline().split())
    time = list(map(int, sys.stdin.readline().split()))
    count = [0] * N
    child = [[] for _ in range(N)]
    for _ in range(K):
        a, b = map(int, sys.stdin.readline().split())
        child[a-1].append(b-1)
        count[b-1] += 1
    w = int(sys.stdin.readline().strip())

    if count[w-1]:
        total = time[::]
        queue = deque([])
        for x in range(N):
            if not count[x]:
                queue.append(x)
                total[x-1] = time[x-1]
        sol(queue)
    else:
        print(time[w-1])

코드 구성

• time 배열 : 건설에 필요한 시간 저장
• count 배열 : 호출된 수 저장으로 최종 반환 시 활용
• child 배열 : 해당 건물 이후에 건설되는 건물 저장
• total 배열 : 건설에 필요한 총 누적 시간 저장
• 시간 초과 방지를 위한 deque 활용
• 먼저 건설되어야 하는 건물이 없다면, queue에 추가
• BFS 방식 탐색, 방문 시 현재 저장값과 새로운 값중 큰 값 저장
• count의 w-1 번째 값이 0이라면, total의 w-1 값 출력
• count의 w-1 번째 값이 처음부터 없었다면, 함수 실행 없이 time의 w-1 값 출력

 

틀린 이유

• count의 유무를 확인 해 넘길 때, x-1이 아닌 x를 넘겨야 함
• count가 0이 되면 해당 건물 이전에 만들어야 하는 건물들이 모두 건설 된 것
  • 해당 건물을 건설하는 시간을 더해줘야 함

---

2차 시도 오답 -> 시간 초과

import sys
from collections import deque

T = int(sys.stdin.readline().strip())
for tc in range(T):
    N, K = map(int, sys.stdin.readline().split())
    time = list(map(int, sys.stdin.readline().split()))
    count = [0] * N
    child = [[] for _ in range(N)]
    for _ in range(K):
        a, b = map(int, sys.stdin.readline().split())
        child[a-1].append(b-1)
        count[b-1] += 1
    w = int(sys.stdin.readline().strip())

    total = time[::]
    queue = deque([])
    for x in range(N):
        if not count[x]:
            queue.append(x)
            total[x] = time[x]
    while queue:
        i = queue.popleft()
        for j in child[i]:
            total[j] = max(total[i] + time[j], total[j])
            queue.append(j)
            count[j] -= 1
            if not count[j-1]:
                queue.append(j)
    print(total[w-1])

코드 변화

• 한 번만 호출될 함수를 정의 하는 대신 코드로 작성
• 먼저 건축되어야 하는 건물들이 모두 건축되면, 본인을 짓기 위해 queue에 추가

 

틀린 이유

• queue.append(j) 부분에서 시간초과 발생 추정

---

최종 정답

# 1. 리스트로 먼저 건설되어야 하는 건물 정보 저장
# 2. BFS 탐색, total 누적 시간 저장
# 3. 먼저 건축되어야 하는 건물이 없을 경우 queue 추가, 건축 시작

# 1차 시도 -> 4% 틀렸습니다.
# 2차 시도 -> 시간 초과

import sys
from collections import deque

T = int(sys.stdin.readline().strip())
for tc in range(T):
    N, K = map(int, sys.stdin.readline().split())
    time = list(map(int, sys.stdin.readline().split()))    # 건축 시간
    count = [0] * N    # 먼저 건축되어야 하는 건물 수
    child = [[] for _ in range(N)]    # 건축 완료 후 건설될 수 있는 건물들
    for _ in range(K):
        a, b = map(int, sys.stdin.readline().split())
        child[a-1].append(b-1)    # 건축 정보 저장
        count[b-1] += 1    # 건축 조건 수 추가
    w = int(sys.stdin.readline().strip())

    total = time[::]
    queue = deque()
    for x in range(N):    # 건축 가능 시 queue 추가
        if not count[x]:
            queue.append(x)
            total[x] = time[x]    # 누적시간 저장
    while queue:
        i = queue.popleft()
        for j in child[i]:    # 건축 정보 리스트 활용
            total[j] = max(total[i] + time[j], total[j])    # 큰 값 저장
            count[j] -= 1    # 건축 조건 건물 수 조정
            if not count[j]:    # 건축 가능 시 queue 추가
                queue.append(j)

    print(total[w-1])

코드 변화

• 이전에 건축되어야 하는 건물들이 모두 건축 된 경우만 queue 추가
  • 시간 초과 방지
  • 불필요한 반복 삭제

---

느낀점

아무래도 BFS로 푸는 문제가 아니었던 것 같다.

내가 푼 방법을 BFS라고 할 수 있는지도 확신이 없어서 알고리즘 개념도 공부해야겠다.