본문 바로가기
✨ Club|Project/파이 \ 𝒩ew𝓣𝓮ams 알고리즘 스터디 | Algorithm

🎶 𝒩ew𝓣𝓮ams ♫ - 정모

by 정람지 2024. 6. 25.

*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)으로 바꿔줄 수 있다

 

예엥..

난...싹난감자


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

건너편의 개발자들

 

니엘이랑 민재