DFS λ¬Έμ
1. λ³μ n μ μΈλΆλ‘λΆν° μ λ ₯λ°μ κ°μ μ μ₯ν©λλ€.
2. ch λΌλ 리μ€νΈλ₯Ό λ§λ€μ΄ μ€λλ€. κ°μ΄ 0 μΌλ‘ ν΄μ n+1 ν¬κΈ°λ‘ λ§λ€μ΄μ€λλ€.
v = 1
3. DFS(1) λ 4λ²μ€μ ν¨μ DFS μ vκ°μ 1μ λ£μ΄ μ€νμν΅λλ€.
4λ²μ€ : ν¨μ DFS μ 1μ΄ λ€μ΄κ°λ©΄,
n(μ¬κΈ°μ nμ 3μΌλ‘ κ°μ νλ€) +1 μ κ°μ 4μ΄λ€.
5λ²μ€ : vκ° n+1 μ κ°λ€λ©΄ λ°λ‘ μλ forλ¬Έμ μ€νμν¨λ€. νμ¬ vμλ 1μ΄ λ€μ΄μκΈ° λλ¬Έμ 1 !=4 μ΄λ―λ‘ 10λ²μ€ elseκ° μ€νμ΄ λλ€.
11λ²μ€: ch[1] =1 μ΄λ―λ‘ ,
μ΄λ κ² λλ€.
v = 2
12λ²μ€ : DFS(v+1) μλ DFS(2)κ° λ κ²μ΄κ³ , DFS(2)λ 4λ²μ€μ μλ ν¨μ DFS μ μ΄λ²μλ 1μ΄μλ 2λ₯Ό λ£μ΄μ μ€νμμΌμ€λ€.
5λ²μ€ : if 2 == 4: κ° λκ³ , μ΄λ κ±°μ§μ΄λ―λ‘, else λ¬ΈμΌλ‘ μ΄λνλ€.
νμ¬ v=2 μμ μμ§λ§μ. κ·ΈλΌ v=2 λ₯Ό κ°μ§κ³ else λ¬Έμ λμ°©νμΌλ,
11λ²μ€: ch[2] =1 μ΄ λλ€.
12λ²μ€: DFS(2+1) λ‘ DFS(3)μ΄ λκ³ , DFS(3)μ λ€μ 4λ²μ€μ μμΉν ν¨μ DFS(v)λ₯Ό νΈμΆνλ€.
v = 3
4λ²μ§Έμ€ : def DFS(3)
5λ²μ§Έμ€ : if 3 == 3+1: < false λ‘ else λ¬ΈμΌλ‘ μ΄λνλ€.
10λ²μ€: ch[3] =1 μ΄λ―λ‘ μλ μ¬μ§μ²λΌ 3λ²μ 1μ μ°μ΄μ€λ€.
12λ²μ€: DFS(4) κ° λκ³ λ λ€μ 4λ²μ€μ μλ ν¨μ DFS(v) λ₯Ό νΈμΆνμ¬ μ΄λνλ€.
v = 4
4λ²μ€: def DFS(4)
5λ²μ€: if 4 == 3+1 μ΄ λκ³ λλμ΄ μ°Έμ΄ λλ€. μ°Έμ΄κΈ° λλ¬Έμ λ°λ‘ μλ forλ¬Έμ μ€νμν¨λ€.
6λ²μ€: for i in range(1, n+1): μ 1λΆν° nκΉμ§ λ°λ³΅νλ μλ―Έμ΄λ€. μ¬κΈ°μ nμ 3μΌλ‘ μ‘μκΈ° λλ¬Έμ
for 1 in range (1, 4)κ° λλ€.
7λ²μ€: if ch[1] ==1 μ΄λΌλ©΄
8λ²μ€ : print λ¬Έμ ν΅νμ¬ i κ° μ¦ λ¦¬μ€νΈ μμ μΈλ±μ€ κ° μ΄ μ°νλ€.
ch μΈλ±μ€κ° 1μΈκ°μ 1, 2, 3 λͺ¨λ λ€ ν΄λΉλλ―λ‘ 1 2 3 μ΄ μΆλ ₯λλ€.