[python] μ μλ³μμ μ§μλ³μ μ 리
μ μλ³μλ main μ€ν¬λ¦½νΈμ μ μΈλκ²μ λ§νλ€.
15 μ€: cntλΌλ λ³μλ₯Ό μμ±κ³Ό λμμ 5λΌλ κ°μ ν λΉν΄μ€λ€.
16 μ€: DFS1() νΈμΆ
17 μ€: DFS2() νΈμΆ
16λ²μ€ μ DFS1() νΈμΆμ νμ¬ 5λ²μ€μ μμΉν DFS1()ν¨μκ° μ€νλλ€.
print(cnt) μ¦ cntλ³μ κ°μ΄ μΆλ ₯λλλ° cnt λΌλ λ³μκ° μκΈ° μμ μ μ§μλ³μμΈμ§ νμΈν©λλ€.
μκΈ°μ μ§μλ³μκ° μλλΌλ©΄ μ μλ³μμΈμ§ νμΈν©λλ€.
λλ€ μλλΌλ©΄ μλ¬κ° λ°μνλ€.
μ¬κΈ°μλ 6λ²μ€μ cntλ μκΈ° μμ μ μ§μλ³μκ° μλλ€. κ·Έλ κΈ° λλ¬Έμ μ μλ³μλ‘ μλνκ² λ©λλ€.
κ·Έλμ 5κ³Ό μΆλ ₯λλ€.
17λ²μ€μ DFS2() νΈμΆ νμ¬ 8λ²μ€μ μμΉν DFS2()ν¨μκ° μ€ν λλ€.
λ§μ½ λ³μcnt κ° 5κ° λ§λ€λ©΄ cnt κ°μ μΆλ ₯νλ μ½λμ΄λ€.
κ·Έλ°λ° μ¬κΈ°μλ cntλ μ§μλ³μμΈμ§ λ¨Όμ νμΈν΄λ³΄λ μλλ€. μ μλ³μλ‘ μλνκ² λλ€.
κ·Έλ κΈ° λλ¬Έμ 5κ° μΆλ ₯λλ€.
λ§μ§λ§ 18λ² μ€ cnt μΆλ ₯ κ° μ 5
κ²°κ³Ό :
κ° μΆλ ₯λλ€.
μ΄λ²μλ 5λ²μ€μ cnt=3 λ§ μΆκ°νλ€.
κ·Έλ¬λ©΄ 6λ²μ€ λ³μ cntλ μΆλ ₯ν λ 15λ²μ€μ cnt=5 λ₯Ό μΆλ ₯νμ§ μκ³ μ§μλ³μ 5λ²μ€ cnt=3 μ λΆλ¬μμ
3μ μΆλ ₯νλ€.
10λ²μ€μ cnt=cnt+1 μ μΆκ°ν΄λ³΄μλ€. μ΄λ κ² λλ©΄ μλ¬κ° λ°μνλλ°. κ·Έμ΄μ κ°
cnt = cnt +1 μμ cntλ μ§μλ³μ μ μΈμΌλ‘ λ³Ό μ μλ€. κ·Έλ°λ° μ§μλ³μ μΈ cntμ κ°μ΄ μ΄λμλ μ μΈλμ΄ μμ§ μλ€.
μ§μλ³μλ‘ μ¬μ©νκΈ° μν΄μλ 8λ² 9λ² μ¬μ΄μ cnt = 1 μ΄λΌλμ§ cntμ κ°μ ν λΉν΄μ£Όλ©΄ ν΄κ²°λλ€.
μλλ©΄ μ μλ³μλ‘ μ¬μ©νκ³ μΆλ€λ©΄
9λ²μ€ μ²λΌ global cnt λ₯Ό μ½λμ λ£μ΄μ£Όλ©΄ μ μλ³μλ‘ cntλ₯Ό μ¬μ©νκ² λλ€.