🎶 𝒩ew𝓣𝓮ams ♫

*g5 s#100..-@$me

g5랜디

21738

골5

사이클 없고

흠

빨간 얼음에서 깊이 우선 탐색해서 펭귄 얼음이 나올 때까지 간 다음에 나올 때

DFS

visited에서 True 개수 세서 저장한 다음에

제일 작은 값 두 개~N에서 빼기

아으으ㅡㅇ시간초과인데??ㅠㅠㅠ!

는? 생각해 보면?

난 지금 모든 빨간 얼음에 대해 DFS를 진행하고 있고?

그냥 펭긴얼음에서 한번만 진행해보면 되는?

는 또 시간초과나고~~!~!~!

는? C++로 바꿔 보면?

은 역시 안 되고

는 아아

DFS내에서 visited.count(True)가 S번 실행되므로

count 함수가 O(N)이라서

O(S(N) * N)이다

이를 매 노드의 깊이를 저장하는 리스트로 관리해서 O(N)으로 바꿔줄 수 있다

예엥..

난...싹난감자

정화언니랑 원밀리언 가기로 햇따

건너편의 개발자들

니엘이랑 민재