본문 바로가기

알고리즘

새로운 시대

New Era · 10번Lv. 3그래프 탐색(BFS·DFS)

새로운 시대

문제 설명

왕좌의 대청에 봉화가 모두 켜지자, 라이언 타운 밖을 가득 메운 평민들의 함성이 왕궁까지 울려 퍼졌습니다. 그날 밤, 위니브 월드에 새로운 시대가 열렸습니다.

다음 날 아침, 라이캣은 동료들을 모아 첫 번째 일을 정했습니다.

"평민도 갈 수 있는 병원을 짓는다냥. 아이들이 배울 학교와, 돌봐 줄 어른이 없는 아이들을 위한 보육원도 함께 짓는다냥."

오래전 어머니를 병원에 모셔 가지 못했던 날, 생선 가게 소년 캣이 했던 다짐이었습니다. 대리인 No.1은 캣네생선의 자금을 내놓았고, 소울곰은 북극 광산에서 캐 온 보석을 꺼냈습니다. 자바독은 고향의 특급 기술자들을 불러 모았고, 개리는 스페이스 스톤으로 자재를 실어 날랐습니다.

"공사가 이렇게 많으면 무엇부터 챙겨야 하는지 검증!?"

"하루라도 늦어지면 전체가 늦어지는 공사부터 챙기면 된다냥. 함께가 아니면, 아무것도 아니다냥!"

공사는 1번부터 n번까지 있습니다. data는 [days, rules]입니다.

  • days[i]는 (i+1)번 공사에 걸리는 날 수입니다.
  • rules의 원소 [a, b]는 "a번 공사가 끝나야 b번 공사를 시작할 수 있다"는 뜻입니다.

공사는 다음 규칙으로 진행합니다.

  1. 일꾼은 충분해서 여러 공사를 동시에 진행할 수 있습니다.
  2. 먼저 끝나야 하는 공사가 없는 공사는 첫날부터 시작할 수 있습니다.
  3. 먼저 끝나야 하는 공사가 있는 공사는 그 공사들이 모두 끝난 다음 날부터 시작할 수 있습니다.
  4. 한 번 시작한 공사는 쉬지 않고 이어서 합니다. 예를 들어 첫날 시작한 3일짜리 공사는 3일째에 끝납니다.

모든 공사를 끝내는 데 걸리는 가장 짧은 날 수를 구하세요. 그리고 그 공사 하나만 하루 늦게 끝나도(그 공사의 날 수가 하루 늘어나도) 모든 공사를 끝내는 날이 늦어지는 공사의 번호를 모두 구하세요.

[가장 짧은 날 수, 하루라도 늦으면 안 되는 공사 번호를 오름차순으로 담은 리스트]를 return 하세요.


제한 사항

  • n(days의 길이)은 1 이상 1,000 이하이고, days의 원소는 1 이상 100 이하의 정수입니다.
  • rules의 길이는 0 이상 5,000 이하입니다. [a, b]에서 a와 b는 1 이상 n 이하의 서로 다른 정수이고, 같은 규칙이 두 번 나오지 않습니다.
  • 규칙을 따라가다 같은 공사로 되돌아오는 경우(순환)는 없습니다. 따라서 모든 공사를 끝낼 수 있습니다.

입출력 예

입력출력
[[3, 2, 4, 1, 2], [[1, 2], [1, 3], [2, 4], [3, 4], [4, 5]]][10, [1, 3, 4, 5]]
[[4, 7, 7], []][7, [2, 3]]
[[2, 3, 3, 1, 3, 2], [[1, 2], [1, 3], [2, 4], [3, 4], [1, 5], [4, 6], [5, 6]]][8, [1, 2, 3, 4, 6]]

입출력 설명

입출력 예 #1

병원 공사입니다. 1번 터 다지기(3일), 2번 약초밭 만들기(2일), 3번 건물 올리기(4일), 4번 진료실 꾸미기(1일), 5번 문 열 준비(2일)라고 해 봅시다.

공사시작끝
1번1일째3일째
2번4일째5일째
3번4일째7일째
4번8일째8일째
5번9일째10일째

모든 공사는 10일째에 끝납니다. 2번 공사는 6일째나 7일째에 끝나도 4번 공사를 8일째에 시작할 수 있어서 전체 일정이 늦어지지 않습니다. 나머지 1·3·4·5번 공사는 하루만 늦어도 모든 공사가 11일째에 끝납니다.

입출력 예 #2

먼저 끝나야 하는 공사가 없으니 세 공사를 첫날 함께 시작합니다. 7일이 걸리고, 7일짜리 2번·3번 공사는 하루만 늦어도 전체가 늦어집니다.

입출력 예 #3

1 → 2 → 4 → 6과 1 → 3 → 4 → 6 모두 2 + 3 + 1 + 2 = 8일이 걸리므로 두 줄에 있는 공사가 모두 하루도 늦으면 안 됩니다. 1 → 5 → 6은 2 + 3 + 2 = 7일이라, 5번 공사는 하루 늦어도 괜찮습니다.

예시 테스트

#입력기대값
1[[3, 2, 4, 1, 2], [[1, 2], [1, 3], [2, 4], [3, 4], [4, 5]]][10, [1, 3, 4, 5]]
2[[4, 7, 7], []][7, [2, 3]]
3[[2, 3, 3, 1, 3, 2], [[1, 2], [1, 3], [2, 4], [3, 4], [1, 5], [4, 6], [5, 6]]][8, [1, 2, 3, 4, 6]]

입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 12개도 함께 채점해요.