Find Eventual Safe States

LogoFind Eventual Safe States - LeetCodeLeetCode

문제 λ²ˆμ—­

λ…Έλ“œκ°€ 0λΆ€ν„° n-1κΉŒμ§€ λ ˆμ΄λΈ”λœ n개의 λ…Έλ“œλ‘œ 이루어진 λ°©ν–₯ κ·Έλž˜ν”„κ°€ μžˆμŠ΅λ‹ˆλ‹€. 
이 κ·Έλž˜ν”„λŠ” 0-인덱슀 기반 2D μ •μˆ˜ λ°°μ—΄ graph둜 ν‘œν˜„λ©λ‹ˆλ‹€. 
μ—¬κΈ°μ„œ graph[i]λŠ” λ…Έλ“œ i에 μΈμ ‘ν•œ λ…Έλ“œλ“€μ˜ μ •μˆ˜ 배열이며, 
μ΄λŠ” λ…Έλ“œ iμ—μ„œ graph[i]의 각 λ…Έλ“œλ‘œ κ°€λŠ” 간선이 μžˆμŒμ„ μ˜λ―Έν•©λ‹ˆλ‹€.

터미널 λ…Έλ“œλž€ λ‚˜κ°€λŠ” 간선이 μ—†λŠ” λ…Έλ“œμž…λ‹ˆλ‹€.
μ•ˆμ „ν•œ λ…Έλ“œλž€ ν•΄λ‹Ή λ…Έλ“œμ—μ„œ μ‹œμž‘ν•˜λŠ” λͺ¨λ“  κ°€λŠ₯ν•œ κ²½λ‘œκ°€ 터미널 λ…Έλ“œ(λ˜λŠ” λ‹€λ₯Έ μ•ˆμ „ν•œ λ…Έλ“œ)둜 
λλ‚˜λŠ” λ…Έλ“œλ₯Ό μ˜λ―Έν•©λ‹ˆλ‹€.

κ·Έλž˜ν”„μ—μ„œ λͺ¨λ“  μ•ˆμ „ν•œ λ…Έλ“œλ₯Ό λ‹΄κ³  μžˆλŠ” 배열을 λ°˜ν™˜ν•˜μ„Έμš”. λ°˜ν™˜ 값은 μ˜€λ¦„μ°¨μˆœμœΌλ‘œ μ •λ ¬λ˜μ–΄μ•Ό ν•©λ‹ˆλ‹€.

이 λ¬Έμ œλŠ” λ°©ν–₯ κ·Έλž˜ν”„ μ—μ„œ "μ•ˆμ „ν•œ λ…Έλ“œ(Safe Nodes)" λ₯Ό μ°ΎλŠ” λ¬Έμ œμž„.

μ•ˆμ „ν•œ λ…Έλ“œλž€ λͺ¨λ“  κ°€λŠ₯ν•œ κ²½λ‘œκ°€ 터미널 λ…Έλ“œ(λ‚˜κ°€λŠ” 간선이 μ—†λŠ” λ…Έλ“œ) λ˜λŠ” λ‹€λ₯Έ μ•ˆμ „ν•œ λ…Έλ“œλ‘œ λλ‚˜λŠ” λ…Έλ“œλ₯Ό 말함.

μ£Όμš” κ°œλ…

  1. 터미널 λ…Έλ“œ(Terminal Node):

    1. λ‚˜κ°€λŠ” 간선이 μ—†λŠ” λ…Έλ“œ. 즉, 더 이상 λ‹€λ₯Έ λ…Έλ“œλ‘œ 갈 수 μ—†λŠ” λ…Έλ“œλ₯Ό 말함.

    2. 예: μ–΄λ–€ λ…Έλ“œμ˜ 인접 λ¦¬μŠ€νŠΈκ°€ λΉ„μ–΄ 있으면 터미널 λ…Έλ“œμž„.

  2. μ•ˆμ „ν•œ λ…Έλ“œ(Safe Node):

    1. ν•΄λ‹Ή λ…Έλ“œμ—μ„œ μ‹œμž‘ν•˜λŠ” λͺ¨λ“  κ²½λ‘œκ°€ λ°˜λ“œμ‹œ 터미널 λ…Έλ“œ λ˜λŠ” λ‹€λ₯Έ μ•ˆμ „ν•œ λ…Έλ“œλ‘œ λλ‚˜λŠ” λ…Έλ“œμž„.

    2. μ•ˆμ „ν•œ λ…Έλ“œλŠ” μ ˆλŒ€ 사이클에 ν¬ν•¨λ˜μ§€ μ•ŠμŒ.

    3. 예λ₯Ό λ“€μ–΄, μ–΄λ–€ λ…Έλ“œμ—μ„œ μΆœλ°œν•΄ μ‚¬μ΄ν΄λ‘œ 듀아가지 μ•Šκ³  λ°˜λ“œμ‹œ 터미널 λ…Έλ“œμ— λ„λ‹¬ν•œλ‹€λ©΄ κ·Έ λ…Έλ“œλŠ” μ•ˆμ „ν•¨.

  3. κ·Έλž˜ν”„ ν‘œν˜„:

    1. κ·Έλž˜ν”„λŠ” 2D 리슀트 ν˜•νƒœλ‘œ 주어짐.

    2. graph[i] λŠ” λ…Έλ“œ i μ—μ„œ λ‚˜κ°€λŠ” 간선이 μ—°κ²°λœ λ…Έλ“œλ“€μ˜ 리슀트λ₯Ό λ‚˜νƒ€λƒ„.

    3. 예 : graph[0] = [1,2] λŠ” λ…Έλ“œ 0μ—μ„œ λ…Έλ“œ 1κ³Ό λ…Έλ“œ 2둜 간선이 μžˆμŒμ„ μ˜λ―Έν•¨.

λͺ©ν‘œ

  • 주어진 κ·Έλž˜ν”„μ—μ„œ λͺ¨λ“  μ•ˆμ „ν•œ λ…Έλ“œ λ₯Ό μ°Ύκ³ , 이λ₯Ό μ˜€λ¦„μ°¨μˆœμœΌλ‘œ μ •λ ¬λœ λ°°μ—΄λ‘œ λ°˜ν™˜ν•˜λŠ” κ²ƒμž„.

문제 ν•΄κ²° 방법

  1. 터미널 λ…Έλ“œ 탐색:

    1. λ¨Όμ € 터미널 λ…Έλ“œλ₯Ό 확인함. μ΄λŠ” λ‚˜κ°€λŠ” 간선이 μ—†λŠ” λ…Έλ“œ

  2. 사이클 감지:

    1. μ–΄λ–€ λ…Έλ“œκ°€ 사이클에 ν¬ν•¨λ˜λ©΄ κ·Έ λ…Έλ“œλŠ” μ•ˆμ „ν•˜μ§€ μ•ŠμŒ.

    2. 사이클에 μ—°κ²°λœ λ…Έλ“œλŠ” μ•ˆμ „ν•œ λ…Έλ“œκ°€ 될 수 μ—†μ—ˆμŒ.

  3. μ•ˆμ „ν•œ λ…Έλ“œ νŒλ³„:

    1. λ…Έλ“œμ—μ„œ μΆœλ°œν•˜λŠ” λͺ¨λ“  κ²½λ‘œκ°€ 터미널 λ…Έλ“œ λ˜λŠ” λ‹€λ₯Έ μ•ˆμ „ν•œ λ…Έλ“œλ‘œλ§Œ μ—°κ²°λœλ‹€λ©΄ κ·Έ λ…Έλ“œλŠ” μ•ˆμ „ν•¨.

  4. κ²°κ³Ό μ •λ ¬:

    1. μ•ˆμ „ν•œ λ…Έλ“œλ“€μ„ μ°Ύμ•„λ‚Έ ν›„ μ˜€λ¦„μ°¨μˆœμœΌλ‘œ 정렬함.

이 문제의 핡심은 κ·Έλž˜ν”„μ—μ„œ 사이클을 ν¬ν•¨ν•˜μ§€ μ•Šκ³  터미널 λ…Έλ“œλ‘œ 도달할 수 μžˆλŠ” λͺ¨λ“  λ…Έλ“œ λ₯Ό μ°Ύμ•„λ‚΄λŠ” 것

μ΄λŸ¬ν•œ λ…Έλ“œλŠ” μ•ˆμ „ν•œ λ…Έλ“œλ‘œ κ°„μ£Όλ˜λ©°, μ΅œμ’…μ μœΌλ‘œ 이 λ…Έλ“œλ“€μ„ μ •λ ¬ν•˜μ—¬ λ°˜ν™˜ν•΄μ•Όν•¨.

PreviousValidParenthesesNextλ‹΅

Last updated

Was this helpful?